線段樹 (區間查詢)

線段樹是一種二叉樹，可視為樹狀陣列的變種，最早出現在2001年，由演算法競賽選手發明。

此資料結構實際應用用途不大，但由於其程式易於實作而被廣泛應用於演算法競賽當中。其用途是在 $O(\log N)$ 查詢一個指定區間內的資訊，並可在同樣的時間複雜度支援更新等操作。

結構

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

基本操作

線段樹所要提供的是查詢一個區間 $[l,r)$ 內的資訊 $f([l,r))$ ，並允許修改操作。要使用線段樹，此資訊必須滿足對於區間 $[l,r)$ 與位於區間內的一點 $m$ ， $f([l,r))$ 要可以由 $f([l,m))$ 、 $f([m,r))$ 求得。例如範圍最值查詢即符合此條件。線段樹維護的資訊在很多時候可以認為是滿足具有半群的性質的資訊。

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

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線段樹是一種由下而上的線段樹，由清華大學的張昆瑋提出。它相對於傳統線段樹的優勢體現在減少了遞歸操作和增加了位元運算等操作以減少常數^[1]。

參考資料

^ 張昆瑋. 统计的力量——线段树全接触. [2014-07-20]. （原始內容存檔於2021-11-04）.

[1] 張昆瑋. 统计的力量——线段树全接触. [2014-07-20]. （原始內容存檔於2021-11-04）.

[1]