线段树 (区间查询)

线段树是一种二元樹，可視為树状数组的變種，最早出現在2001年，由算法競賽選手發明。^{[來源請求]}

线段树是一种将数组存储为树的数据结构。这允许高效地回答数组上的范围查询，同时仍然足够灵活以允许快速修改数组。这包括查找连续数组元素 $a[l\dots r]$ 的总和，或在 $O(\log n)$ 时间内找到此类范围内的最小元素（范围最值查询）。在回答此类查询之间，线段树允许通过替换一个元素甚至更改整个子段的元素来修改数组（例如，将所有元素 $a[l\dots r]$ 分配给任何值，或为子段中的所有元素增加一个值）。^[1]

通常，线段树是一种非常灵活的数据结构，可以用它解决大量问题。此外，还可以应用更复杂的操作并回答更复杂的查询。特别是，线段树可以轻松推广到更大的维度。例如，使用二维线段树，只需 $O(\log ^{2}n)$ 时间即可回答给定矩阵中某个子矩形的总和或最小值查询。线段树的一个重要特性是它们只需要线性量的内存，通常需要4n个顶点来处理大小为n的数组。^[1]

結構

線段樹是一個平衡的二叉树，它将每个长度不为1的区间划分成左右两个区间递归求解。令整個區間的長度為N，則其有N個葉節點，每個葉節點代表一個單位區間，每個內部結點代表的區間為其兩個兒子代表區間的聯集。这种数据结构可以方便的进行大部分的区间操作。

基本操作

線段樹所要提供的是查詢一個區間 $[l,r)$ 內的子問題的答案 $f([l,r))$ ，並允許修改操作。要使用線段樹，此資訊大部分情況下需要滿足對於區間 $[l,r)$ 與位於區間內的一點 $m$ ， $f([l,r))$ 要可以由 $f([l,m))$ 、 $f([m,r))$ 求得。例如範圍最值查詢即符合此條件。线段树维护的信息大部分情況需要符合半群的性質，但有例外，像是可以動態維護最大子數列問題，雖無法透過 $f([l,m))$ 、 $f([m,r))$ 求得 $f([l,r))$ ，但可以透過維護多個資料在同一線段樹節點維護每個區間的子問題。

代码中, $rt$ 指的是 $root$ , 当前子树的根节点; $l,r$ 指的是当前子树所统计的区间 $[l,r]$ 利用完全二叉堆的性质来保存节点编号, 所以 $rt<<1$ (即 $rt\times 2$ )是左子树的节点, $rt<<1|1$ (即 $rt\times 2+1$ )是右子树的节点在查询和成端更新操作中的L和R是指修改或者查询的区间

节点数据向上更新

将子节点的值更新到父节点，即合併兩個子問題。

/* 对于区间求和 */ void push_up(int rt) {     tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]; }  /* 对于区间求最大值 */ void push_up(int rt) {     tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]); }

节点懒惰标记下推

对于区间求和, 原子数组值需要加上lazy标记乘以子树所统计的区间长度。 len为父节点统计的区间长度, 则len - (len >> 1) (即 $len-[len/2]$ )为左子树区间长度, len >> 1 (即 $[len/2]$ )为右子树区间长度。

void push_down(int rt, int len) {     tree[rt << 1] += lazy[rt] * (len - (len >> 1));     lazy[rt << 1] += lazy[rt];     tree[rt << 1 | 1] += lazy[rt] * (len >> 1);     lazy[rt << 1 | 1] += lazy[rt];     lazy[rt] = 0; }

对于区间求最大值, 子树的值不需要乘以长度, 所以不需要传递参数len。

void push_down(int rt) {     tree[rt << 1] += lazy[rt];     lazy[rt << 1] += lazy[rt];     tree[rt << 1 | 1] += lazy[rt];     lazy[rt << 1 | 1] += lazy[rt];     lazy[rt] = 0; }

建树

新建一棵长度N的线段树，有時也會使用更新函式代替以減少代碼量。

#define lchild rt << 1, l, m #define rchild rt << 1 | 1, m + 1, r void build(int rt = 1, int l = 1, int r = N) {     if (l == r) { std::cin >> tree[rt]; return; }     int m = (l + r) >> 1;     build(lchild); build(rchild);     push_up(rt); }

更新

单点更新, 不需要用到lazy标记

#define lchild rt << 1, l, m #define rchild rt << 1 | 1, m + 1, r void update(int p, int delta, int rt = 1, int l = 1, int r = N) {     if (l == r) {         tree[rt] += delta;         return;     }     int m = (l + r) >> 1;     if (p <= m) update(p, delta, lchild);     else update(p, delta, rchild);     push_up(rt); }

成段更新, 需要用到lazy标记来提高时间效率。如果要求修改区间，把所有包含在区间中的节点都遍历一次、修改一次，时间复杂度太高。所以要有 「懒惰标记」（lazy标记）。懒惰标记就是通过延迟对节点信息的更改，从而减少不必要的操作次数。每次执行修改时，通过打标记的方法表明该节点对应的区间在某一次操作中被更改，但不更新该节点的子节点的信息，实质性的修改则在下一次访问带有标记的节点时才进行。

#define lchild rt << 1, l, m #define rchild rt << 1 | 1, m + 1, r void update(int L, int R, int delta, int rt = 1, int l = 1, int r = N) {     if (L <= l && r <= R) {         tree[rt] += delta * (r - l + 1);         lazy[rt] += delta;         return;     }     if (lazy[rt]) push_down(rt, r - l + 1);     int m = (l + r) >> 1;     if (L <= m) update(L, R, delta, lchild);     if (R > m)  update(L, R, delta, rchild);     push_up(rt); }

区间查询

#define lchild rt << 1, l, m #define rchild rt << 1 | 1, m + 1, r int query(int L, int R, int rt = 1, int l = 1, int r = N) {     if (L <= l && r <= R) return tree[rt];     if (lazy[rt]) push_down(rt, r - l + 1);     int m = (l + r) >> 1, ret = 0;     if (L <= m) ret += query(L, R, lchild);     if (R > m)  ret += query(L, R, rchild);     return ret; }

可直接使用的编程模板

#include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std;  namespace SegTree { 	#define maxn 1000000 	class SegmentTree { 		#define lson (o<<1) 		#define rson (o<<1|1) 		#define mid ((l+r)>>1) 		public : 			int addv[maxn], maxv[maxn], minv[maxn], sumv[maxn]; 			int arr[maxn]; 			int N; 		private:int _max(const int& _, const int& __) { return _>__?_:__; } 		private:int _min(const int& _, const int& __) { return _<__?_:__; } 		public : int pushup(int o) { 			minv[o] = _min(minv[lson], minv[rson]); 			maxv[o] = _max(maxv[lson], maxv[rson]); 			sumv[o] = sumv[lson] + sumv[rson]; 			return 0; 		} 		public : int pushdown(int o, int l, int r) { 			if(addv[o] == 0) return -1; 			addv[lson] += addv[o]; addv[rson] += addv[o]; 			minv[lson] += addv[o]; minv[rson] += addv[o]; 			maxv[lson] += addv[o]; maxv[rson] += addv[o]; 			sumv[lson] += addv[o] * (mid-l+1); sumv[rson] += addv[o] * (r-mid); 			addv[o] = 0; 		} 		public : int Build(int o, int l, int r) { 			addv[o] = 0; 			if(l == r) { 				maxv[o] = arr[l];minv[o] = arr[l];sumv[o] = arr[l]; 				return 0; 			} 			Build(lson, l, mid); 			Build(rson, mid+1, r); 			pushup(o); 			return 0; 		} 		public : int optadd(int o, int l, int r, int ql, int qr, int addval) { 			if(ql > r or qr < l) return 0; 			if(ql <= l and r <= qr) { 				addv[o] += addval; 				sumv[o] += addval * (r-l+1); 				return 0; 			} 			pushdown(o, l, r); 			optadd(lson, l, mid, ql, qr, addval); 			optadd(rson, mid+1, r, ql, qr, addval); 			pushup(o); 		} 		public : int query_sum(int o, int l, int r, int ql, int qr) { 			if(ql > r or qr < l) return 0; 			if(ql <= l and r <= qr) { 				return sumv[o]; 			} 			pushdown(o, l, r); 			return query_sum(lson, l, mid, ql, qr) + query_sum(rson, mid+1, r, ql, qr); 		} 		public : int query_min(int o, int l, int r, int ql, int qr) { 			if(ql > r or qr < l) return 0; 			if(ql <= l and r <= qr) { 				return minv[o]; 			} 			pushdown(o, l, r); 			return _min(query_min(lson, l, mid, ql, qr), query_min(rson, mid+1, r, ql, qr)); 		} 		public : int query_max(int o, int l, int r, int ql, int qr) { 			if(ql > r or qr < l) return 0; 			if(ql <= l and r <= qr) { 				return maxv[o]; 			} 			pushdown(o, l, r); 			return _max(query_max(lson, l, mid, ql, qr), query_max(rson, mid+1, r, ql, qr)); 		} 	}; }  //End of SegmentTree using namespace SegTree;

变种

zkw线段树是一种自底向上的线段树，由清华大学的张昆玮提出。它相对于传统线段树的优势体现在减少了递归操作和增加了位运算等操作以减少常数^[2]。

參考資料

^ ^1.0 ^1.1 https://cp-algorithms.com/data_structures/segment_tree.html （页面存档备份，存于互联网档案馆） Segment Tree – CP-Algorithms
^ 张昆玮. 统计的力量——线段树全接触. [2014-07-20]. （原始内容存档于2021-11-04）.

[cp-algorithms-1] 1.0 ^1.1 https://cp-algorithms.com/data_structures/segment_tree.html （页面存档备份，存于互联网档案馆） Segment Tree – CP-Algorithms

[2] 张昆玮. 统计的力量——线段树全接触. [2014-07-20]. （原始内容存档于2021-11-04）.

[1]

[2]

查论编计算机科学中的树
二叉树	二元搜尋樹笛卡尔树 MVP树 Top tree（英语：Top tree） T树线索二叉树
自平衡二叉查找树	AA树 AVL树左倾红黑树红黑树替罪羊树伸展树树堆加权平衡树
B树	B+树 B*树 B^x树 UB树 2-3树 2-3-4树 (a,b)-树（英语：(a,b)-tree）跳舞樹（英语：Dancing tree） H树
堆	二叉堆二项堆斐波那契堆左偏树配对堆斜堆范恩德蟒蛇樹（英语：Van Emde Boas tree）
Trie	后缀树基数树三叉查找树 X-快速前缀树 Y-快速前缀树 AC自动机
二叉空间分割（BSP）树	四叉树八叉树 k-d树隐式k-d树 VP树
非二叉树	指数树（英语：Exponential tree）融合树（英语：Fusion tree） PQ树（英语：PQ tree） SPQR树（英语：SPQR tree）
空间数据分割树	R树 R*树 R+树 X树 M树線段樹 (儲存區間) 线段树 (区间查询) 可持久化线段树希尔伯特R树优先R树
其他树	散列日历散列树手指樹（英语：Finger tree）顺序统计树度量樹（英语：Metric tree）覆蓋樹（英语：Cover tree） BK树二重連鎖樹（英语：Doubly chained tree） iDistance（英语：iDistance） Link-cut tree（英语：Link-cut tree） Log-structured merge-tree（英语：Log-structured merge-tree）树状数组哈希树