前言
线段树是算法竞赛中常用的用来维护
区间信息
的数据结构。
线段树可以在
O
(
l
o
g
N
)
O(logN)
O
(
l
o
g
N
)
的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值)等操作。
简介
线段树将每个长度不为
1
1
1
的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。
线段树的结构如下：
简单的来讲，对于线段树内任意一颗非叶子结点而言，他表示的区间是
[
l
,
r
]
[l,r]
[
l
,
r
]
，其左儿子表示的区间是
[
l
,
m
i
d
]
[l, mid]
[
l
,
mi
d
]
，其右儿子表示的区间是
[
m
i
d
+
1
,
r
]
[mid+1, r]
[
mi
d
+
1
,
r
]
，其中
m
i
d
=
⌊
l
+
r
2
⌋
mid=\lfloor\frac{l+r}2\rfloor
mi
d
=
⌊
2
l
+
r
⌋
。
堆式存储
空间
如果
n
n
n
为叶子结点数量，那么数组要开
2
l
o
g
(
n
)
+
1
2^{log(n)+1}
2
l
o
g
(
n
)
+
1
这么大，如果懒得算就开直接 4n。
建树
考虑递归建树，dfs遍历一遍即可，要在回溯时pushup（即维护当前区间的值，因为下面更改了）。
区间修改
单点修改相当于
l
=
r
l = r
l
=
r
的情况 ， 我就不啰嗦了。
可以考虑直接修改表示区间被
[
l
,
r
]
[l,r]
[
l
,
r
]
包含的所有节点。但如果这样做时间肯定爆，所以我们采用
l
a
z
y
t
a
g
lazytag
l
a
zy
t
a
g
技术。
就是懒标记拉。我们令
t
a
g
[
k
]
tag[k]
t
a
g
[
k
]
表示节点
k
k
k
欠下其子树的更新值，区间修改时点到即止（即不去更新被完全包含的结点的子树），然后呢什么时候访问到这个结点再下传标记给它的子节点（注意修改时也要下传，因为如果不下传标记，子节点会pushup一个错误额值）。
我们可以记下传标记为pushdown，这个操作实在接着向下递归之前。
区间查询
直接将所有被
[
l
,
r
]
[l,r]
[
l
,
r
]
包含的区间合并起来即可，记得下传标记。
模板（区间和）
struct SegamentTree {
static const int MAX = 1e5;
struct TreeNode {
ll val, tag;
}tr[MAX<<2];
inline void pushup(int &k) {
tr[k].val = tr[k<<1].val + tr[k<<1|1].val;
}
inline void pushdown(int &k, int &l, int &r, int &mid) {
if(tr[k].tag) {
tr[k<<1].val += tr[k].tag * (mid-l+1), tr[k<<1|1].val += tr[k].tag * (r-mid);
if(l < mid) tr[k<<1].tag += tr[k].tag, tr[k<<1|1].tag += tr[k].tag; // 叶子结点不需要标记
tr[k].tag = 0;
}
}
void build(int k, int l, int r) {
// k:结点编号 [l, r] 结点k的表示的区间。
if(l == r) {
tr[k].val = a[l];
return;
}
int mid = l + (r - l >>1);
build(k<<1, l, mid);
build(k<<1|1, mid+1, r);
pushup(k);
}
ll query(int k, int l, int r, int x, int y) {
// k, l, r 同上 [x, y] 查询区间
if(x <= l && r <= y) // 如果被包含
return tr[k].val;
int mid = l + (r - l >> 1); ll res = 0;
pushdown(k, l, r, mid);
if(x <= mid) res = query(k<<1, l, mid, x, y); // 左区间与查询区间有交集
if(y > mid) res += query(k<<1|1, mid+1, r, x, y); // 右区间与查询区间有交集
return res;
}
void update(int k, int l, int r, int x, int y, int t) {
// k, l, r, x, y 同上 t 表示增加值
if(x <= l && r <= y) {
tr[k].val += (r - l + 1) * t;
if(l != r) tr[k].tag += t;
return;
}
int mid = l + (r - l >> 1);
pushdown(k, l, r, mid);
if(x <= mid) update(k<<1, l, mid, x, y, t);
if(y > mid) update(k<<1|1, mid+1, r, x, y, t);
pushup(k);
}
};
标记永久化
标记永久化就是不上下传递标记，在不爆的前提下可以优化常数，也更加方便使用。
修改时，把所有不被修改区间完全包含和被修改区间一级包含（即第一个被枚举到的完全包含区间）结点累计上他总共能获得的贡献，然后在一级包含结点上打标记。
查询时，累计枚举到一级包含结点前的所有tag，返回
t
a
g
s
u
m
∗
l
e
n
tagsum*len
t
a
g
s
u
m
∗
l
e
n
，其中
t
a
g
s
u
m
tagsum
t
a
g
s
u
m
指标记和，
l
e
n
len
l
e
n
指的是这一节点表示的区间的长度。
Code
ll query(int k, int l, int r, int x, int y, ll sum) {
if(x <= l && r <= y)
return tr[k].val + sum * (r - l + 1);
sum += tr[k].tag;
int mid = l + (r - l >> 1); ll res = 0;
if(x <= mid) res = query(k<<1, l, mid, x, y, sum);
if(y > mid) res += query(k<<1|1, mid+1, r, x, y, sum);
return res;
}
void update(int k, int l, int r, const int& x, const int& y, const int& t) {
tr[k].val += (std::min(y, r) - std::max(x, l) + 1) * t; // 他应得的贡献
if(x <= l && r <= y) {
tr[k].tag += t;
return;
}
int mid = l + (r - l >> 1);
if(x <= mid) update(k<<1, l, mid, x, y, t);
if(y > mid) update(k<<1|1, mid+1, r, x, y, t);
}
动态开点
动态开点就是不一下开满整一棵树，用到哪开到哪。可以在结构体内建立ls和rs表示左右儿子分别存在哪，这里就不贴代码了。