该题是一道简单的区间求和题，跟杭电的敌兵布阵很是想象，这里是使用Splay写的。
Splay就是伸展的意思，因为该树在使用过程中会大量的执行Rotate函数，该函数就是在保持二叉树中序遍历不变的情况下，使树的结构发生变化。
该题中，二叉树中存储的值并不一定要求是顺序的，满足左孩子比根节点小，右孩子比根节点大，其大小只是一个构树时的顺序关系。每次旋转能够时确保目标节点一定要在旋转节点的下方，因为任何Rotate操作旋转节点的深度都是在降低的。Splay数的作用在于能够Splay操作选出区间，首先建立两个理论上的无穷小和无穷大点，如果选择区间[a, b]，那么将
a-1号节点旋转到根节点，再将b+1号节点旋转到根节点之下，由于b+1 > a-1 恒成立，所以b+1号节点一定是其右孩子，根据中序遍历的关系，a-1之后就是b+1的左子树，再就是b+1了，因此我们就选择出了区间[a, b]。再在上面做一些操作即可。代码如下：
#include#include #include #define L(x) tree[x].ch[0]#define R(x) tree[x].ch[1]#define Key L(R(rt))#define MAXN 100005using namespace std;int N, Q, queue[MAXN], seq[MAXN], rt, front;struct Node{ int di, v, ch[2], lazy, fa; long long s; void New(int x, int y) { di = 1, v = s = x, fa = y; lazy = ch[0] = ch[1] = 0; } void Add(int x) { lazy += x; s += (long long)di * x; v += x; }}tree[MAXN];void push_up(int x){ tree[x].di = 1+tree[L(x)].di+tree[R(x)].di; tree[x].s = tree[x].v+tree[L(x)].s+tree[R(x)].s;}void push_down(int x){ if (tree[x].lazy) { tree[L(x)].Add(tree[x].lazy); tree[R(x)].Add(tree[x].lazy); tree[x].lazy = 0; }}void rotate(int x, int f){ int y = tree[x].fa, z = tree[y].fa; push_down(y), push_down(x); tree[y].ch[!f] = tree[x].ch[f]; tree[ tree[y].ch[!f] ].fa = y; tree[x].ch[f] = y; tree[y].fa = x; tree[x].fa = z; if (z) { tree[z].ch[R(z) == y] = x; } push_up(y);}void splay(int x, int obj){ int y, z; while (tree[x].fa != obj) { y = tree[x].fa, z = tree[y].fa; if (z == obj) { rotate(x, L(y) == x); } else { if (x == L(y) && y == L(z)) { rotate(y, 1), rotate(x, 1); } else if (x == R(y) && y == R(z)) { rotate(y, 0), rotate(x, 0); } else if (x == R(y) && y == L(z)) { rotate(x, 0), rotate(x, 1); } else { rotate(x, 1), rotate(x, 0); } } } push_up(x);}void select(int x, int k, int obj){ if (k != tree[L(x)].di) { if (k < tree[L(x)].di) { select(L(x), k, obj); } else { select(R(x), k-tree[L(x)].di-1, obj); } } else { splay(x, obj); if (obj == 0) { rt = x; } }}void build(int &x, int l, int r, int fa){ if (l > r) return; int m = (l+r) >> 1; x = queue[++front]; tree[x].New(seq[m], fa); build(L(x), l, m-1, x); build(R(x), m+1, r, x); push_up(x);}void init(){ for (int i = 0; i < MAXN; ++i) { queue[i] = i; } rt = queue[++front]; tree[rt].New(0, 0); R(rt) = queue[++front]; tree[R(rt)].New(0, rt); build(Key, 1, N, R(rt)); // 构造出两个边界点以及题给的信息区间// push_up(R(rt));// push_up(rt);}void travel(int x){ if (x) { travel(L(x)); printf("di=%d, s=%lld, v=%d, fa.v=%d\n", tree[x].di, tree[x].s, tree[x].v, tree[tree[x].fa].v); travel(R(x)); }}int main(){ char op[5]; int x, y, z; while (scanf("%d %d", &N, &Q) == 2) { for (int i = 1; i <= N; ++i) { scanf("%d", &seq[i]); } init(); while (Q--) { scanf("%s %d %d", op, &x, &y); select(rt, x-1, 0); select(rt, y+1, rt); if (op[0] == 'C') { scanf("%d", &z); tree[Key].Add(z); } else { printf("%lld\n", tree[Key].s); } } } return 0;}