题目大意

    一个数列，每次操作可以是将某区间数字都加上一个相同的整数，也可以是询问一个区间中所有数字的和。（这里区间指的是数列中连续的若干个数）对每次询问给出结果。

思路

1. 伸展树的一般规律

    对于区间的查找更新操作，可以考虑使用伸展树、线段树等数据结构。这里使用伸展树来解决。 

    伸展树对数组进行维护的核心思想是，将需要维护的一组数单独提取出来，形成一棵子树（一般为整棵树的根节点的右子节点的左孩子节点 为根），然后再这个子树上进行操作。此时进行某些操作（如 ADD, SUM 等），只需要在根节点上做个标记，进行延迟处理（即在之后真正访问子节点时候才对子节点进行实际的更新操作），这样可以节省时间。 

    每次对树的节点进行修改（比如DELETE, INSERT等）之后，都要进行维护信息，此时需要Update一下，然后将该节点旋转至树根。 

     且在寻找一个区间的起始点对应在树中的节点的时候，都要将该节点所需要的所有信息带给该节点，这就要求在从根节点向下寻找该节点的时候，将路径上的所有节点（即该节点的祖先节点）上的标记都往下传，即PushDown。 

    

2. 针对本题的分析

    此题中的节点信息需要维护 data（节点的数据大小）、size（以该节点为根的子树的大小）、lazy（节点需要加的数值）、sum（以该节点为根的子树所代表的区间在此刻的区间和） 

    在每次找到一个区间，形成一棵子树，对该区间进行加一个数值D的时候，需要在该子树根节点位置的lazy加上值D而不需要下放到每个树中的子节点，同时该节点的sum值需要加上 D*节点的size。 

    在节点下放的PushDown过程中，进行如下操作：

1 //向下更新信息 2 void PushDown(int node){ 3     int left = gTreeNode[node].child[0]; 4     int right = gTreeNode[node].child[1]; 5      6     long long tmp_add = gTreeNode[node].lazy; 7     if (tmp_add){ 8         gTreeNode[node].data += tmp_add; 9 10         gTreeNode[left].lazy += tmp_add;11         gTreeNode[left].sum += (gTreeNode[left].size * tmp_add);12 13         gTreeNode[right].lazy += tmp_add;14         gTreeNode[right].sum += (gTreeNode[right].size * tmp_add);15         gTreeNode[node].lazy = 0;16     }17 }

    在节点的Update过程中，需要进行如下操作：

1 //维护本节点信息 2 void Update(int node){     3     gTreeNode[node].sum = gTreeNode[node].data; 4     gTreeNode[node].size = 1; 5     int left = gTreeNode[node].child[0], right = gTreeNode[node].child[1]; 6     if (left){ 7         gTreeNode[node].size += gTreeNode[left].size; 8         gTreeNode[node].sum += gTreeNode[left].sum; 9     }10     if (right){11         gTreeNode[node].size += gTreeNode[right].size;12         gTreeNode[node].sum += gTreeNode[right].sum;13     }14     //注意，此时的sum值属于以该节点为根的子树，因此每次都需要从 gTreeNode[node].data 开始加起，而不应该保存原来的值。（这个好像不直观，但画图是可以证明在Splay中，这个sum值是可以保证始终为以该节点为根的子树区间和的）15 }

　　以及需要注意数据的范围， data、lazy和sum均需要为 64位整数。

实现(c++)

#define _CRT_SECURE_NO_WARNINGS#include
      
       #include
       
        #define MIN(a,b) a
        
          end){        return 0;    }    if (beg == end){        gTreeNode[gNodeCount].data = gTreeNode[gNodeCount].sum = gNumber[beg];        return gNodeCount++;    }    int mid = (beg + end) / 2;    int left = BuildTree(beg, mid - 1);    int right = BuildTree(mid + 1, end);    gTreeNode[gNodeCount].data = gTreeNode[gNodeCount].sum = gNumber[mid];    LinkNode(gNodeCount, left, 0);    LinkNode(gNodeCount, right, 1);    Update(gNodeCount);    return gNodeCount++;}//zig or zag旋转void Rotate(int x){    if (x == gRootIndex){        return;    }    int y = gTreeNode[x].parent;    PushDown(y);    PushDown(x);    int d = gTreeNode[x].child_dir;    int z = gTreeNode[y].parent;    LinkNode(z, x, gTreeNode[y].child_dir);    LinkNode(y, gTreeNode[x].child[!d], d);    LinkNode(x, y, !d);    Update(y);    if (y == gRootIndex){        gRootIndex = x;    }}//旋转操作，将node节点旋转到 f 节点下方void Splay(int x, int f){    if (x == f){        return;    }    PushDown(x);    int y = gTreeNode[x].parent, z = 0;    while (y != f){        z = gTreeNode[y].parent;        if (z == f){            Rotate(x);            break;        }        if (gTreeNode[x].child_dir == gTreeNode[y].child_dir){ //一字型旋转            Rotate(y);            Rotate(x);        }        else{ //之字形旋转            Rotate(x);            Rotate(x);        }        y = gTreeNode[x].parent;    }    Update(x);}//获取伸展树中 第k个节点的indexint GetKthInTree(int k){    int node = gRootIndex, left, tmp_size;    while (node){        PushDown(node); //注意要将与该节点有关的信息带下去        left = gTreeNode[node].child[0];        tmp_size = gTreeNode[left].size;        if (!left){
    //left 为空节点            if (k == 1){                return node;            }            else{                node = gTreeNode[node].child[1];                k--;                continue;            }        }        if (tmp_size + 1 == k){            return node;        }        else if (tmp_size >= k){            node = left;        }        else{            node = gTreeNode[node].child[1];            k -= (tmp_size + 1);        }    }    return -1;}//选择区间，返回由该区间构成的子树的节点。节点为 根节点的右子节点的左子节点int SelectInterval(int x, int y){    if (x <= 0 || y > gNodeCount){        printf("fuck this splay tree!!!\n");        return -1;    }    if (x == 1 && y == gNodeCount - 1){        return gRootIndex;    }    int node;    if (x == 1){        node = GetKthInTree(y + 1);        Splay(node, 0);        return gTreeNode[node].child[0];    }    if (y == gNodeCount - 1){        node = GetKthInTree(x - 1);        Splay(node, 0);        return gTreeNode[node].child[1];    }    int node_beg = GetKthInTree(x - 1);    Splay(node_beg, 0);    int node_end = GetKthInTree(y + 1);    Splay(node_end, gRootIndex);    return gTreeNode[node_end].child[0];}void Add(int x, int y, int d){    int node = SelectInterval(x, y);    gTreeNode[node].lazy += d;    gTreeNode[node].sum += gTreeNode[node].size * d;    Splay(node, 0);}long long GetSum(int x, int y){    int node = SelectInterval(x, y);    //获得节点之后，一定要进行更新！！！    PushDown(node);    Update(node);    return gTreeNode[node].sum;}void debug(int node){    if (node){        debug(gTreeNode[node].child[0]);        printf("node %d, parent = %d, left = %d, right = %d, data = %d, sum = %d, lazy = %d\n",            node, gTreeNode[node].parent, gTreeNode[node].child[0], gTreeNode[node].child[1],            gTreeNode[node].data, gTreeNode[node].sum, gTreeNode[node].lazy);        debug(gTreeNode[node].child[1]);    }}int main(){    int node_num, query_num;    gNodeCount = 1;    scanf("%d%d", &node_num, &query_num);    for (int i = 0; i < node_num; i++){        scanf("%d", gNumber + i);    }    gRootIndex = BuildTree(0, node_num - 1); //递归的方式构造一棵开始就平衡的二叉树    gTreeNode[gRootIndex].parent = 0; //根    char op[10];    int x, y, tmp;    for (int i = 0; i < query_num; i++){        //        debug(gRootIndex);        scanf("%s", op);        if (op[0] == 'C'){            scanf("%d%d%d", &x, &y, &tmp);            Add(x, y, tmp);        }        else if (op[0] == 'Q'){            scanf("%d%d", &x, &y);            printf("%lld\n", GetSum(x, y));        }        }    return 0;}