一颗最简单的线段树orz。。。但是感觉还是拍得好麻烦。。。
只支持区间加和区间查询
#include<iostream> #include<cstdlib> #include<cstdio> #include<algorithm> using namespace std; int a[2000010],n,m; typedef long long ll; struct inlinetree{ int l,r; ll s,lazy; }lt[34000100]; inline void pushdown(int x) { if(!lt[x].lazy) return; lt[x<<1].s+=lt[x].lazy*(lt[x<<1].r-lt[x<<1].l+1); //修改左儿子区间和 lt[x<<1|1].s+=lt[x].lazy*(lt[x<<1|1].r-lt[x<<1|1].l+1); //修改右儿子区间和 lt[x<<1].lazy+=lt[x].lazy; //传递lazy给左右儿子 lt[x<<1|1].lazy+=lt[x].lazy; lt[x].lazy=0; //传递完毕将lazy清零 } inline void change(int u,int l,int r,ll d) { if(l<=lt[u].l && lt[u].r<=r) //当前访问到的标号区间恰好被需要修改的区间覆盖 { lt[u].s+=(lt[u].r-lt[u].l+1)*d; //当前整个区间和增加 lt[u].lazy+=d; //lazy 增加 起到作用???? return; } pushdown(u); //传递当前区间lazy(给区间的两个儿子) int mid=(lt[u].l+lt[u].r) >> 1; if(l>mid) change(u<<1|1,l,r,d); //如果当前区间只位于左儿子或者右儿子 else if(r<=mid) change(u<<1,l,r,d); else //当前区间跨越两个儿子 { change(u<<1,l,mid,d); change(u<<1|1,mid+1,r,d); } lt[u].s=lt[u<<1].s+lt[u<<1|1].s; //修改区间和 } inline int query(int u,int l,int r) { if(l<=lt[u].l && lt[u].r<=r) //当前访问到的标号区间恰好被询问的区间覆盖 return lt[u].s; pushdown(u); //传递lazy给儿子 int mid=(lt[u].l+lt[u].r) >> 1; if(l>mid) return query(u<<1|1,l,r); //如果当前区间只位于左儿子或者右儿子 else if(r<=mid) return query(u<<1,l,r); else //当前区间跨越两个儿子 return query(u<<1,l,mid)+query(u<<1|1,mid+1,r); //查询区间和 } inline void build(int u,int l,int r) { lt[u].l=l; //当前编号区间左端点 lt[u].r=r; //当前编号区间右端点 lt[u].lazy=lt[u].s=0; //初始化lazy和区间和的值 if(l==r) //当区间分成单点 { lt[u].s=(ll)a[l]; //单点权值存入 return; } int mid=(l+r) >> 1; build(u<<1,l,mid); //分成两个儿子继续建树 build(u<<1|1,mid+1,r); lt[u].s=lt[u<<1].s+lt[u<<1|1].s; //区间和即为儿子们的区间和 } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); build(1,1,n); //建树 while(m) { m--; int q; scanf("%d",&q); if(q==1) { int l0,r0,d0; scanf("%d%d%d",&l0,&r0,&d0); change(1,l0,r0,(ll)d0); } else { int l99,r99; scanf("%d%d",&l99,&r99); printf("%lld ",query(1,l99,r99)); } } return 0; }