题意:给你一个数列,要求你完成区间更新,区间求和的操作.
也是线段树的模板题,但是这里作为伸展树的练习题：
SplayTree学习参照资料：
1.Crash《运用伸展树解决数列维护问题》
2. http://www.cnblogs.com/kuangbin/archive/2013/04/21/3034081.html
/**
Splay树入门
成段更新+区间更新
**/#include<cstdio>
#include<iostream>
#include<cstring>
#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);}}}}