线段树
2024-06-06 21:45:41
发布于:上海
15阅读
0回复
0点赞
装作没有看见标题
维护单点加,区间和呀,那不线段树裸题吗。
哦,标题是树状数组啊。但是我很蒻,不会树状数组,也看不懂什么 。但是我会线段树呀。于是,就有了这篇题解。
我写的是区间修改的change函数,把读入的单点当作区间处理。实际上可以简化成单点修改的change。大家可以自己试一试哦。
#include <iostream>
#include <cstdio>
using namespace std;
#define MAXN 500000
#define m(l,r) ((l+r)>>1)
#define ls(k) (k<<1)
#define rs(k) ((k<<1)|1)
struct node{
int l,r,dat,tag;
}t[4*MAXN+5];
int a[MAXN+1];
void build(int p, int l, int r){
t[p].l=l;
t[p].r=r;
t[p].tag=0;
if(l==r){t[p].dat=a[l]; return;}
int mid=m(l,r);
build(ls(p),l,mid);
build(rs(p),mid+1,r);
t[p].dat=t[ls(p)].dat+t[rs(p)].dat;
}
inline void down(int p){
if(t[p].tag){
t[ls(p)].dat+=t[p].tag*(t[ls(p)].r-t[ls(p)].l+1);
t[rs(p)].dat+=t[p].tag*(t[rs(p)].r-t[rs(p)].l+1);
t[ls(p)].tag+=t[p].tag;
t[rs(p)].tag+=t[p].tag;
t[p].tag=0;
}
}
void change(int p,int x,int y,int z){
if(x<=t[p].l && y>=t[p].r){
t[p].dat+=z*(t[p].r-t[p].l+1);
t[p].tag+=z;
return;
}
down(p);
int mid=m(t[p].l,t[p].r);
if(x<=mid) change(ls(p),x,y,z);
if(y>mid) change(rs(p),x,y,z);
t[p].dat=t[ls(p)].dat+t[rs(p)].dat;
}
int ask(int p,int x,int y){
if(x<=t[p].l && y>=t[p].r) return t[p].dat;
down(p);
int mid=m(t[p].l,t[p].r);
int ans=0;
if(x<=mid) ans+=ask(ls(p),x,y);
if(y>mid) ans+=ask(rs(p),x,y);
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
for(int i=1;i<=m;i++)
{
int q,x,y;
cin>>q;
if(q==1){
cin>>x>>y;
change(1,x,x,y);
}
else {
cin>>x>>y;
cout<<ask(1,x,y)<<endl;
}
}
return 0;
}
这里空空如也
有帮助,赞一个