線段樹 (區間查詢)

線段樹是一種二元樹，可視為樹狀陣列的變種，最早出現在2001年，由演算法競賽選手發明。^{[來源請求]}

關於用以儲存區間或線段的資料結構（區間樹），請見「線段樹 (儲存區間)」。

線段樹是一種將陣列儲存為樹的資料結構。這允許高效地回答陣列上的範圍查詢，同時仍然足夠靈活以允許快速修改陣列。 這包括尋找連續陣列元素${\displaystyle a[l\dots r]}$ 的總和，或在${\displaystyle O(\log n)}$ 時間內找到此類範圍內的最小元素（範圍最值查詢）。在回答此類查詢之間，線段樹允許通過替換一個元素甚至更改整個子段的元素來修改陣列（例如，將所有元素${\displaystyle a[l\dots r]}$ 分配給任何值，或為子段中的所有元素增加一個值）。^[1]

通常，線段樹是一種非常靈活的資料結構，可以用它解決大量問題。此外，還可以應用更複雜的操作並回答更複雜的查詢。特別是，線段樹可以輕鬆推廣到更大的維度。例如，使用二維線段樹，只需${\displaystyle O(\log ^{2}n)}$ 時間即可回答給定矩陣中某個子矩形的總和或最小值查詢。線段樹的一個重要特性是它們只需要線性量的主記憶體，通常需要4n個頂點來處理大小為n的陣列。^[1]

結構

線段樹是一個平衡的二元樹，它將每個長度不為1的區間劃分成左右兩個區間遞迴求解。令整個區間的長度為N，則其有N個葉節點，每個葉節點代表一個單位區間，每個內部結點代表的區間為其兩個兒子代表區間的聯集。這種資料結構可以方便的進行大部分的區間操作。

基本操作

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

代碼中, ${\displaystyle rt}$指的是${\displaystyle root}$, 當前子樹的根節點; ${\displaystyle l,r}$指的是當前子樹所統計的區間${\displaystyle [l,r]}$利用完全二元堆積的性質來儲存節點編號, 所以${\displaystyle rt<<1}$(即${\displaystyle rt\times 2}$)是左子樹的節點, ${\displaystyle rt<<1|1}$(即${\displaystyle 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) (即 ${\displaystyle len-[len/2]}$)為左子樹區間長度, len >> 1 (即 ${\displaystyle [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]。