查看“︁线段树 (区间查询)”︁的源代码

{{多個問題|
{{Overly detailed}}
{{copypaste}}
{{refimprove|time=2017-03-10T10:09:44+00:00}}
}}
{{NoteTA
|G1= IT
}}
{{Otheruses|other=用以儲存區間或線段的資料結構（区间树）|線段樹 (儲存區間)}}
'''线段树'''是一种[[二元樹]]，可視為[[树状数组]]的變種，{{cn|最早出現在2001年，由算法競賽選手發明。}}

线段树是一种将[[数组]]存储为树的数据结构。这允许高效地回答数组上的范围查询，同时仍然足够灵活以允许快速修改数组。
这包括查找连续数组元素<math>a[l \dots r]</math> 的总和，或在<math>O(\log n)</math> 时间内找到此类范围内的最小元素（[[范围最值查询]]）。在回答此类查询之间，线段树允许通过替换一个元素甚至更改整个子段的元素来修改数组（例如，将所有元素<math>a[l \dots r]</math> 分配给任何值，或为子段中的所有元素增加一个值）。<ref name="cp-algorithms">https://cp-algorithms.com/data_structures/segment_tree.html {{Wayback|url=https://cp-algorithms.com/data_structures/segment_tree.html |date=20220507091134 }} Segment Tree – CP-Algorithms</ref>

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

==結構==

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

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

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

=== 节点数据向上更新 ===
将子节点的值更新到父节点，即合併兩個子問題。
<syntaxhighlight lang=cpp>
/* 对于区间求和 */
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]);
}
</syntaxhighlight>

=== 节点懒惰标记下推 ===
对于区间求和, 原子数组值需要加上lazy标记乘以子树所统计的区间长度。
len为父节点统计的区间长度, 则len - (len >> 1) (即 <math> len-[len/2] </math>)为左子树区间长度, len >> 1 (即 <math> [len/2] </math>)为右子树区间长度。
<syntaxhighlight lang=cpp>
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;
}
</syntaxhighlight>
对于区间求最大值, 子树的值不需要乘以长度, 所以不需要传递参数len。
<syntaxhighlight lang=cpp>
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;
}
</syntaxhighlight>

=== 建树 ===
新建一棵长度N的线段树，有時也會使用更新函式代替以減少代碼量。
<syntaxhighlight lang=cpp>
#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);
}
</syntaxhighlight>

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

=== 可直接使用的编程模板 ===
<syntaxhighlight lang="cpp">
#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;
</syntaxhighlight>

== 变种 ==
[[zkw线段树]]是一种自底向上的线段树，由[[清华大学]]的张昆玮提出。它相对于传统线段树的优势体现在减少了递归操作和增加了位运算等操作以减少常数<ref>{{Cite web |url = http://wenku.baidu.com/link?url=57dSmipYHQx56SfyjgSXf62-gsRw7Fmg3xrMjLzdu12LroANGLvCWPUW1kOSFsVrmqfOK64xvmYw8MtZkUX49O27ZupjnBo7CD72I0L2Ou3 |title = 统计的力量——线段树全接触 |author = 张昆玮 |access-date = 2014-07-20 |archive-date = 2021-11-04 |archive-url = https://web.archive.org/web/20211104003159/https://wenku.baidu.com/link?url=57dSmipYHQx56SfyjgSXf62-gsRw7Fmg3xrMjLzdu12LroANGLvCWPUW1kOSFsVrmqfOK64xvmYw8MtZkUX49O27ZupjnBo7CD72I0L2Ou3 |dead-url = no }}</ref>。

== 參考資料 ==
{{reflist}}

{{计算机科学中的树}}

[[Category:数据结构|X]]