Ruibin_Ningh
其实已经写好一大半了,只是因为懒没有全写完一直在拖
推导
存储
首先我们要存储整个树
我们知道线段树是一颗完全二叉树
对一一个节点 $i$ ,它的左儿子是 $2i$ ,其右儿子是 $2i+1$,这很好证明,因为完全二叉树的性质
那么对一个数组 a ,我们把它的左端点和右端点 $[l,r]$ 设为根节点,并设根节点的编号为1,将区间一分为二,设mid=(l+r)>>1 ,数学表达式为$\lfloor l+r \rfloor $ ,(l+r的向下取整)
我们想到可以用递归解决这个问题,定义build(id,l,r) 表示区间 $[l,r]$ 的编号为 id ,可以写出代码
void build(int id,int l,int r){
if(l==r){ tree[id]=a[l]; return; }
int mid=(l+r)>>1;
build(id<<1, l, mid);
build(id<<1|1, mid+1, r);
tree[id]=tree[id<<1]+tree[id<<1|1];
}操作
像视频中的一样,我们用线段树维护一个最大值,每次操作选择区间 $[l,r]$ 将区间每个数+ $x$ ,
如果你听不明白
这里我做了一个网页实现了可视化,链接线段树-1755576145367.html
线段树可视化
当然觉得我可视化做的不行的也可以看另一个网站的,个人感觉也不错
模板
视频讲的是维护最大值,这里的模板是求和的
模板(区间求和)
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<ll>tree,lazy;
// 初始化线段树数组
void init(int n){tree.assign(4*n+5,0);lazy.assign(4*n+5,0);}
// 上推操作：维护父节点的值
void pull(int id){tree[id]=tree[id<<1]+tree[id<<1|1];}
// 将区间 [l,r] 全部加上 v（懒标记+更新节点值）
void apply(int id,int l,int r,ll v){tree[id]+=v*(r-l+1);lazy[id]+=v;}
// 下推懒标记，把当前节点的标记分发给子节点
void push(int id,int l,int r){
if(lazy[id]==0)return;
int m=(l+r)>>1;
apply(id<<1,l,m,lazy[id]);
apply(id<<1|1,m+1,r,lazy[id]);
lazy[id]=0;
}
// 建树：用数组 a 初始化线段树
void build(int id,int l,int r,const vector<ll>&a){
if(l==r){tree[id]=a[l];return;}
int m=(l+r)>>1;
build(id<<1,l,m,a);
build(id<<1|1,m+1,r,a);
pull(id);
}
// 区间加法：把 [L,R] 内每个元素都加 v
void add(int id,int l,int r,int L,int R,ll v){
if(L<=l&&r<=R){apply(id,l,r,v);return;}
push(id,l,r);
int m=(l+r)>>1;
if(L<=m)add(id<<1,l,m,L,R,v);
if(R>m)add(id<<1|1,m+1,r,L,R,v);
pull(id);
}
// 区间求和：查询 [L,R] 的元素和
ll sumq(int id,int l,int r,int L,int R){
if(L<=l&&r<=R)return tree[id];
push(id,l,r);
int m=(l+r)>>1;ll s=0;
if(L<=m)s+=sumq(id<<1,l,m,L,R);
if(R>m)s+=sumq(id<<1|1,m+1,r,L,R);
return s;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int n;cin>>n;
vector<ll>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
init(n);
build(1,1,n,a);
int q;cin>>q;
while(q--){
int op;cin>>op;
if(op==1){
int L,R;ll v;cin>>L>>R>>v;
add(1,1,n,L,R,v); // 区间加
}else{
int L,R;cin>>L>>R;
cout<<sumq(1,1,n,L,R)<<"\n"; // 区间和
}
}
}
区间最大值+区间加
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<ll>tree,lazy;
void init(int n){tree.assign(4*n+5,0);lazy.assign(4*n+5,0);}
void pull(int id){tree[id]=max(tree[id<<1],tree[id<<1|1]);}
void apply(int id,ll v){tree[id]+=v;lazy[id]+=v;}
void push(int id,int l,int r){
if(lazy[id]==0)return;
int m=(l+r)>>1;
apply(id<<1,lazy[id]);
apply(id<<1|1,lazy[id]);
lazy[id]=0;
}
void build(int id,int l,int r,const vector<ll>&a){
if(l==r){tree[id]=a[l];return;}
int m=(l+r)>>1;
build(id<<1,l,m,a);
build(id<<1|1,m+1,r,a);
pull(id);
}
void add(int id,int l,int r,int L,int R,ll v){
if(L<=l&&r<=R){apply(id,v);return;}
push(id,l,r);
int m=(l+r)>>1;
if(L<=m)add(id<<1,l,m,L,R,v);
if(R>m)add(id<<1|1,m+1,r,L,R,v);
pull(id);
}
ll maxq(int id,int l,int r,int L,int R){
if(L<=l&&r<=R)return tree[id];
push(id,l,r);
int m=(l+r)>>1; ll res=LLONG_MIN;
if(L<=m)res=max(res,maxq(id<<1,l,m,L,R));
if(R>m)res=max(res,maxq(id<<1|1,m+1,r,L,R));
return res;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int n;cin>>n;
vector<ll>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
init(n);
build(1,1,n,a);
int q;cin>>q;
while(q--){
int op;cin>>op;
if(op==1){
int L,R;ll v;cin>>L>>R>>v;
add(1,1,n,L,R,v);
}else{
int L,R;cin>>L>>R;
cout<<maxq(1,1,n,L,R)<<"\n";
}
}
}