线段树的结构
为什么叫线段树？
因为它是把原序列以及其子序列（一个个线段）组织成一棵树的形式。树的根节点为原序列，子节点依次对半分序列，直到叶节点，叶节点是单个数，也没办法再往下分了。
例如[1，7]
可以发现：
-
原本的区间，在最底层其实是一个元素构成的叶节点。
-
从根节点向下递归地过程中，节点的长度逐渐缩小，类似一个不断二分的过程，最后确定为一个点。
-
整棵线段树中，所有节点的个数是小于4n的（n是区间、线段的长度、也即叶节点个数）
还可以看出线段树将近是（最后一层不符合）一颗满二叉树，因此可以直接采用堆存储方式。
因此某一段 u 的
- 父节点是
u>>1 - 左儿子是
u<<1 - 右儿子是
u<<1|1
又因为一颗线段树最多是一颗满二叉树，而满二叉树的最后一层是 \(n\) 个点，前面的点数是 \(n−1\) ，所以一共要 \(2×n−1\) 的空间
但由于线段树有可能最后一层节点还有子节点，比如说 \(n=10\) 的时候，如图：
最后一层是多出来的，而最后一层节点最多 \(2×n\) 个节点，最坏情况下就最右边两个节点，最右下角的一个节点的编号是 \(2×n−1+2×n=4×n−1\) ，所以线段树一般开 \(4×n\)。
存储的属性是：（一般而言）
- 结点所表示区间（线段）的左端点L
- 结点所表示区间（线段）的右端点R
- 结点所表示区间（线段）的和sum
代码
//一般使用结构体来存储线段树,空间大小开四倍
struct Node{
int l,r; //维护的区间
int v; //维护的信息
} tree[N*4];
建树
思路
递归遍历初始区间：
-
如果这个节点不是叶子节点，那么就分别遍历左子树和右子树
-
如果是叶子节点
把表示的区间记录下来，
把线段树维护的信息也记录下来，维护的信息在叶子节点上基本上就是这个数本身 -
递归回来的时，利用儿子节点的信息更新父亲节点的信息
时间复杂度 \(O(logn)\)
代码push_up+build
//利用它的两个儿子来算一下它的当前节点信息
void push_up(int u)
{
tr[u].sum=tr[u<<1].sum + tr[u<<1|1].sum;//左儿子 u<<1 ,右儿子 u<<1|1
}
/*第一个参数，当前节点编号，第二个参数，左边界，第三个参数，右边界*/
void build(int u,int l,int r)
{
//如果当前已经是叶节点了，那我们就直接赋值就可以了
if(l==r)tr[u]={l,r,w[r]};
else
{
tr[u]={l,r};//存储当前点表示的区间
int mid=l+r>>1;//计算边界
build(u<<1,l,mid);//递归左儿子
build(u<<1|1,mid+1,r);//递归右儿子
push_up(u);//做完两个儿子之后push_up，更新一下当前节点信息
}
}
查询
思路
我们从根节点（根节点一定包含所有点，既包含修改区间）出发，一直往下走，直到当前区间中的元素全部都是被修改元素。
- 当左区间包含整个被修改区间时，我们就递归到左区间；
- 当右区间包含整个被修改区间时，我们就递归到右区间；
否则区间的样子就如下图所示：
此时该怎么办呢？
我们可以发现，被修改区间中的元素间，两两之间都不会产生影响。
所以，我们可以把被修改区间分解成两段，
- 使得其中的一段完全在左区间，
- 另一端完全在右区间。
很明显，直接在 \(mid\) 的位置将该区间切开是最好的。如下图所示：
如果当前区间包含了查找区间的话就直接返回值。
时间复杂度 \(O(nlogn)\)
代码query
query操作，用来查询某一段区间内的信息,
查询最大值：
//从u（根节点）节点开始查询[l,r]区间内的某一信息
int query(int u,int l,int r){
if(tree[u].l>=l&&tree[u].r<=r) return tree[u].v; //说明这一段的信息已经被完全包含，因此不需要继续向下递归，直接返回即可
//否则需要判断该递归那一边
//用 res 来表示一下我们的最大值
int res=0;
int mid=tree[u].l+tree[u].r >> 1;
if(l<=mid) res=max(res,query(u<<1,l,r)); //看一下我们当前区间的中点和左边有没有交集
if(mid<r) res=max(res,query(u<<1|1,l,r)); //看一下我们当前区间的中点和左边有没有交集
//切记是mid<r，无等号
return res;
}
查询区间和：
int query(int u,int l,int r)
{
if(l<=tr[u].l&&tr[u].r<=r)return tr[u].sum;
int mid=tr[u].l+tr[u].r>>1;
//先判断一下和左边有没有交集
int sum=0;//用 sum 来表示一下我们的总和
if(mid>=l)//看一下我们当前区间的中点和左边有没有交集
sum+=query(u<<1,l,r);
if(r>=mid+1)//看一下我们当前区间的中点和右边有没有交集
sum+=query(u<<1|1,l,r);
return sum;
}
单点修改
我们通过二分查找的形式找到要修改的点，然后把找的过程上的链都修改一下。
代码
用来修改某一叶子节点并更新其所有父节点
void modify(int u,int x,int v){ //从u节点开始递归查找，将编号为x的节点的值修改为v
if(tree[u].l==x&&tree[u].r==x) tree[u].v=v;
else{
int mid=tree[u].l+tree[u].r>>1;
//看一下 x 是在左半边还是在右半边
if(x<=mid) modify(u<<1,x,v);
else modify(u<<1|1,x,v);
push_up(u);
}
}
区间修改
引入懒标记和push_down。
懒标记含义：
修改区间包含当前区间，就在这个节点上打个标记。
如果一个点上打的一个懒标记，那么表示这个点的所有子节点都要变化这个懒标记（可以是加除 max ， min ， GCD 等等），
注意：
- 懒标记不包含当前点！
- 如果一个点有懒标记，要先把他的懒标记下传给他的儿子。
（不向下传会遇到：左半部分+x，右半部分+y的情况，导致数据不匹配）
代码push_down+modify
区间加法为例
void push_down (int u) { //下传标记函数
auto &root = tr[u],&left = tr[u << 1],&right = tr[u << 1 | 1]; //加了引用符号只要修改这个变量就会修改他被赋值的变量
if (root.sum_tag) { //有懒标记才下传
left.tag += root.tag,left.sum += (LL)(left.r - left.l + 1) * root.tag; //这里的子节点要加上懒标记，因为懒标记不包括当前节点
right.tag += root.tag,right.sum += (LL)(right.r - right.l + 1) * root.tag; //同理
root.tag = 0; //懒标记记得清零
}
}
void modify (int u,int l,int r,int d) { //当前遍历到的点下标是u，要将区间[l,r]增加d
if (l <= tr[u].l && tr[u].r <= r) {
tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
tr[u].sum_tag += d; //一个点所有的子节点都加上d，而前一行时加上根节点的数，因为不包括根节点。
return ;
}
push_down (u); //一定要分裂，只要记牢在递归左右区间之前，就要分裂
int mid = tr[u].l + tr[u].r >> 1; //注意时tr[u].l和tr[u].r
if (l <= mid) modify (u << 1,l,r,d); //左边有修改区间，就递归左半边
if (r >= mid + 1) modify (u << 1 | 1,l,r,d); //右边有修改区间，就递归右半边
push_up (u); //要记得要把这个点的信息更新一下
}
单点修改模板代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 200010;
int m, p;
struct Node
{
int l, r;
int v; // 区间[l, r]中的最大值
}tr[N * 4];
void pushup(int u) // 由子节点的信息，来计算父节点的信息
{
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].v; // 树中节点，已经被完全包含在[l, r]中了
int mid = tr[u].l + tr[u].r >> 1;
int v = 0;
if (l <= mid) v = query(u << 1, l, r);
if (r > mid) v = max(v, query(u << 1 | 1, l, r));
return v;
}
void modify(int u, int x, int v)
{
if (tr[u].l == x && tr[u].r == x) tr[u].v = v;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
int main()
{
int n = 0, last = 0;
scanf("%d%d", &m, &p);
build(1, 1, m);
int x;
char op[2];
while (m -- )
{
scanf("%s%d", op, &x);
if (*op == 'Q')
{
last = query(1, n - x + 1, n);
printf("%d\n", last);
}
else
{
modify(1, n + 1, ((LL)last + x) % p);
n ++ ;
}
}
return 0;
}
区间修改模板代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int w[N];
struct Node
{
int l, r;
LL sum, add;
}tr[N * 4];
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u)
{
auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if (root.add)
{
left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add;
right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add;
root.add = 0;
}
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, w[r], 0};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int d)
{
if (tr[u].l >= l && tr[u].r <= r)
{
tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
tr[u].add += d;
}
else // 一定要分裂
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, d);
if (r > mid) modify(u << 1 | 1, l, r, d);
pushup(u);
}
}
LL query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL sum = 0;
if (l <= mid) sum = query(u << 1, l, r);
if (r > mid) sum += query(u << 1 | 1, l, r);
return sum;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
build(1, 1, n);
char op[2];
int l, r, d;
while (m -- )
{
scanf("%s%d%d", op, &l, &r);
if (*op == 'C')
{
scanf("%d", &d);
modify(1, l, r, d);
}
else printf("%lld\n", query(1, l, r));
}
return 0;
}
原文
作者：incra
链接：https://www.acwing.com/file_system/file/content/whole/index/content/6505356/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
作者：Perf
链接：https://www.acwing.com/solution/content/61919/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
作者：Elegant
链接：https://www.acwing.com/solution/content/40394/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。