本文共 3480 字，大约阅读时间需要 11 分钟。
题意:给你一个数列,要求你完成区间更新,区间求和的操作.
也是线段树的模板题,但是这里作为伸展树的练习题：
SplayTree学习参照资料：
1.Crash《运用伸展树解决数列维护问题》
2.
/**Splay树入门成段更新+区间更新**/#include#include #include #define keyv ch[ch[root][1]][0]using namespace std;const int maxn = 1e5+999;int pre[maxn],ch[maxn][2],ssize[maxn],root,tot1;//父节点.左右孩子.子树规模，根节点,节点数量int key[maxn];/**节点的值*/int add[maxn];/**加号标记*/long long sum[maxn];/**区间和*/int s[maxn],tot2;//内存池int a[maxn];int n,q;void newnode(int &r,int father,int k){ if(tot2)r = s[tot2--]; else r = ++tot1; pre[r] = father; ssize[r] = 1; key[r] = k; add[r] = 0; sum[r] = 0; ch[r][0] = ch[r][1] = 0;}void update(int r,int v){ if(r==0) return ; add[r] += v; key[r] += v; sum[r] += (long long)v*ssize[r];}void pushup(int r){ ssize[r] = ssize[ch[r][0]]+ssize[ch[r][1]]+1; sum[r] = sum[ch[r][0]] + sum[ch[r][1]] + key[r];}void pushdown(int r){ if(add[r]) { update(ch[r][0],add[r]); update(ch[r][1],add[r]); add[r] = 0; }}void build(int &x,int l,int r,int father){ if(l>r)return; int m = (l+r)>>1; newnode(x,father,a[m]); build(ch[x][0],l,m-1,x); build(ch[x][1],m+1,r,x); pushup(x);}//0 1 左右void init(){ for(int i=1; i<=n; i++)scanf("%d",a+i); root = tot1 = tot2=0; ch[root][0] = ch[root][1] = pre[root] = ssize[root] = add[root] = sum[root] =0; key[root] = 0; newnode(root,0,-111); newnode(ch[root][1],root,-111);/**添加边界，大小随意*/ build(keyv,1,n,ch[root][1]); pushup(ch[root][1]); pushup(root);}void Rotate(int x,int kind){ int y = pre[x]; pushdown(y);/**先更y*/ pushdown(x); ch[y][!kind] = ch[x][kind]; pre[ch[x][kind] ] =y; if(pre[y]) { ch[pre[y]][ch[pre[y]][1]==y]=x; } pre[x] = pre[y]; ch[x][kind] = y; pre[y] = x; pushup(y);/**更新下面的*/}/**把节点r调整至goal下面*/void splay(int r,int goal){ pushdown(r); while(pre[r]!=goal) { if(pre[pre[r] ] == goal) Rotate(r,ch[pre[r]][0]==r); else { int y = pre[r]; int kind = ch[pre[y]][0]==y; if(ch[y][kind] == r)/**之字形*/ { Rotate(r,!kind); Rotate(r,kind); } else /**一字型*/ { Rotate(y,kind); Rotate(r,kind); } } } pushup(r);/**最后更新r,这里请参照 Crash《运用伸展树解决数列维护问题》 */ if(goal == 0 )root = r;}int kth(int r,int k){ pushdown(r); int t = ssize[ch[r][0]]+1; if(t==k) return r; if(t>k)return kth(ch[r][0],k); else return kth(ch[r][1],k-t);}int getmin(int r){ pushdown(r); while(ch[r][0]) { r = ch[r][0]; pushdown[r]; } return r;}int getmax(int r){ pushdown(r); while(ch[r][1]) { r = ch[r][1]; pushdown[r]; } return r;}void ADD(int l,int r,int d){ splay(kth(root,l),0);/**比l-1大*/ splay(kth(root,r+2),root);/**比r+1小*/ update(keyv,d); pushup(ch[root][1]); pushup(root);}long long query(int l,int r){ splay(kth(root,l),0); splay(kth(root,r+2),root); return sum[keyv];}int main(){ while(scanf("%d%d",&n,&q)==2) { init(); char op[9]; int x,y,z; while(q--) { scanf("%s",op); if(op[0] == 'Q') { scanf("%d%d",&x,&y); printf("%I64d\n",query(x,y)); } else { scanf("%d%d%d",&x,&y,&z); ADD(x,y,z); } } }}
转载地址：http://dbyci.baihongyu.com/