线段树 (区间查询) 线段树是一种二元树，可视为树状数组的变种，最早出现在2001年，由算法竞赛选手发明。 此资料结构实际应用用途不大，但由于其程式易于实作而被广泛应用于算法竞赛当中。其用途是在formula_1查询一个指定区间内的资讯，并可在同样的时间复杂度支援更新等操作。 结构. 线段树是一个平衡的二叉树，它将每个长度不为1的区间划分成左右两个区间递归求解。令整个区间的长度为N，则其有N个叶节点，每个叶节点代表一个单位区间，每个内部结点代表的区间为其两个儿子代表区间的联集。这种数据结构可以方便的进行大部分的区间操作。 基本操作. 线段树所要提供的是查询一个区间formula_2内的资讯formula_3，并允许修改操作。要使用线段树，此资讯必须满足对于区间formula_2与位于区间内的一点formula_5，formula_3要可以由formula_7、formula_8求得。例如范围最值查询即符合此条件。线段树维护的信息在很多时候可以认为是满足含半群的性质的信息。 代码中, rt指的是root, 当前子树的根节点; l, r指的是当前子树所统计的区间formula_9利用完全二叉堆的性质来保存节点编号, 所以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的线段树。 void build(int rt = 1, int l = 1, int r = N) { int m = (l + r) » 1; build(lchild); build(rchild); push_up(rt); 更新. 单点更新, 不需要用到lazy标记 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(L, R, delta, rchild); push_up(rt); 区间查询. int query(int L, int R, int rt = 1, int l = 1, int r = N) { if (L m) ret += query(L, R, rchild); return ret; 可直接使用的编程模板. 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; 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 r or qr r or qr 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线段树是一种自底向上的线段树，由清华大学的张昆玮提出。它相对于传统线段树的优势体现在减少了递归操作和增加了位运算等操作以减少常数。 相关链接. http://dongxicheng.org/structure/segment-tree/ （页面存档备份，存于-{zh-cn:互联网档案馆;zh-tw:网际网路档案馆;zh-hk:互联网档案馆;zh-sg:互联网档案馆;}-） https://cp-algorithms.com/data_structures/segment_tree.html （页面存档备份，存于-{zh-cn:互联网档案馆;zh-tw:网际网路档案馆;zh-hk:互联网档案馆;zh-sg:互联网档案馆;}-） Segment Tree – CP-Algorithms