H - 线段树 1
题意
区间修改区间查询
线段树简介
线段树是一颗二叉树，他能通过树的分支将一块区间划分为数个单元区间，每个单元区间对应线段树中的一个叶结点。
如图，一颗具有15个结点的完全二叉树就可以用于划分一块 [1,8] 的区间为单元区间。
- 对于线段树中的一个结点：
左儿子表示区间：\([L，(L+R)/2]\)
右儿子表示区间：\([(L+R)/2+1，R]\) - 对于节点编号采用顺序编号
左儿子编号：\(2x\)
右儿子编号：\(2x+1\)
即由上到下，由左到右进行编号
作用
线段树主要用于维护区间信息，支持区间加，减，乘，取模等操作
代码分析
定义一个结构体节点，每个结点都具有四个值，lazy值、存储值、区间左右边界，定义一个结构体便于表示及存储
struct node{
int l,r; //l,r为该节点表示的区间
LL lz,pre; //lz代表这个点的lazy值（lazy标记功能是对暂时不需要的区间进行延迟累积更新，达到优化的目的），pre代表这个点储存的值(区间和)
}tr[N * 4]; //经验值，枚举区间长度从 1−10^6，最多有2n个叶子节点，2n+n+n/2+... < 4n,则所用到的节点数最多是 4n
接下来就是建树的过程
左儿子编号：\(2p\) 左儿子表示区间：\([L，(L+R)/2]\)
右儿子编号：\(2p+1\) 右儿子表示区间：\([(L+R)/2+1，R]\)
//初始化维护线段树
void buildtree(int p,int l,int r){ //递归建树，表示p点储存的区间为[l,r]
tr[p] = {l,r};
if(l == r){ //递归到区间只剩一个节点时赋值
tr[p].pre = a[r];
return;
}
int mid = tr[p].l + tr[p].r >> 1; //划分左右儿子 l+r )>>1 即 (l+r)/2
buildtree(p << 1,l,mid); //递归建左树 p<<1 即 p*2
buildtree(p << 1 | 1,mid + 1,r); //递归建右树 p<<1|1 即 p*2+1(注意偶数|1才可以视为+1)
tr[p].pre = tr[p << 1].pre + tr[p << 1 | 1].pre; //递归到底层后用子节点实现对父节点的更新（左右儿子之和）
}
更新操作：
void update(int p,int l,int r,int x){
if(tr[p].l >= l && tr[p].r <= r){ //如果需要更新的区间完全覆盖节点区间
tr[p].pre += (LL)x * len(p); //加上整个节点长度的x
tr[p].lz += x; //维护lazy标记
return; //由于已覆盖该节点，其子节点区间只会是该节点的子集，因此可以利用lazy标记，后续需要使用更小的区间时再进行更新
} //更新完全覆盖
lazy(p); //如果需要更新的区间没有完全覆盖节点区间，下传lazy值（因为现在要用到更小的区间）
int mid = tr[p].l + tr[p].r >> 1; //二分
if(l <= mid)update(p << 1,l,r,x); //如果需要更新的区间涉及左节点，那么递归下去继续更新
if(r > mid)update(p << 1 | 1,l,r,x); //如果需要更新的区间涉及右节点，那么递归下去继续更新
tr[p].pre = tr[p << 1].pre + tr[p << 1 | 1].pre; //由于左右节点已经被更新，那么父节点也需要更新
}
示例：
将 \([1,4]\) 加\(1\)，则结点\(1\)打上懒标记\(1\)
将 \([1,3]\) 加\(1\)，此时懒标记需要下传
结点\(1\)懒标记清空
结点\(2\)，结点3打上懒标记\(1\)，同时将值修改
下传后再处理\([1,3]\)加\(1\)
将 \([1,3]\) 加\(1\)，则结点\(2\)的懒标记再加上\(1\)，接点\(6\)值直接加\(1\)
可见一个点的懒标记值与点的值没有关系，仅影响子节点的值，懒标记存在则子节点值需要修改
下传lazy操作:
void lazy(int p){
if(tr[p].lz){
tr[p << 1].pre += tr[p].lz * len(p << 1); //左节点更新储存值
tr[p << 1 | 1].pre += tr[p].lz * len(p << 1 | 1); //右节点更新储存值
tr[p << 1].lz += tr[p].lz; //传递lazy值给左节点
tr[p << 1 | 1].lz += tr[p].lz; //传递lazy值给右节点
tr[p].lz = 0; //清空当前节点lazy值
}
}
输出节点长度:
int len(int p){
return tr[p].r - tr[p].l + 1;
}
输出区间和：
LL query(int p,int l,int r){
if(tr[p].l >= l && tr[p].r <= r){ //如果询问的区间完全覆盖节点区间
return tr[p].pre; //返回节点值（部分区间和）
}
lazy(p); //否则就下传lazy值
LL ans = 0;
int mid = tr[p].l + tr[p].r >> 1; //递归寻找所有适配区间
if(l <= mid)ans += query(p << 1,l,r);
if(r > mid)ans += query(p << 1 | 1,l,r);
return ans; //返回答案
}
最终代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 1e6+10;
const int M = 2e5+10;
int n,m;
int a[N];
struct node{
int l,r;
LL lz,pre;
}tr[N * 4];
void buildtree(int p,int l,int r){
tr[p] = {l,r};
if(l == r){
tr[p].pre = a[r];
return;
}
int mid = tr[p].l + tr[p].r >> 1;
buildtree(p << 1,l,mid);
buildtree(p << 1 | 1,mid + 1,r);
tr[p].pre = tr[p << 1].pre + tr[p << 1 | 1].pre;
}
int len(int p){
return tr[p].r - tr[p].l + 1;
}
void lazy(int p){
if(tr[p].lz){
tr[p << 1].pre += tr[p].lz * len(p << 1);
tr[p << 1 | 1].pre += tr[p].lz * len(p << 1 | 1);
tr[p << 1].lz += tr[p].lz;
tr[p << 1 | 1].lz += tr[p].lz;
tr[p].lz = 0;
}
}
void update(int p,int l,int r,int x){
if(tr[p].l >= l && tr[p].r <= r){
tr[p].pre += (LL)x * len(p);
tr[p].lz += x;
return;
} //更新完全覆盖
lazy(p);
int mid = tr[p].l + tr[p].r >> 1;
if(l <= mid)update(p << 1,l,r,x);
if(r > mid)update(p << 1 | 1,l,r,x);
tr[p].pre = tr[p << 1].pre + tr[p << 1 | 1].pre;
}
LL query(int p,int l,int r){
if(tr[p].l >= l && tr[p].r <= r){
return tr[p].pre;
}
lazy(p);
LL ans = 0;
int mid = tr[p].l + tr[p].r >> 1;
if(l <= mid)ans += query(p << 1,l,r);
if(r > mid)ans += query(p << 1 | 1,l,r);
return ans;
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; i ++ )cin >> a[i];
buildtree(1,1,n);
while(m -- ){
int op,l,r,x;
cin >> op >> l >> r;
if(op == 1){
cin >> x;
update(1,l,r,x);
}
else{
cout << query(1,l,r) << nl;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}