题目大意

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

思路

    对于区间的查找更新操作，可以考虑使用伸展树、线段树等数据结构。这里使用线段树来解决。需要注意的是，对于一个区间的增加操作，如果每次都走到叶子节点进行更新，则必定超时，因此lazy方法来解决。即如果能从当前节点获得所需要的信息，则不必走到子节点。

实现(c++)

#define _CRT_SECURE_NO_WARNINGS#include
     
      #include
      
       using namespace std;#define MAX_COUNT 100005#define MAX(a, b) a>b? a:b#define MIN(a, b) a
       
        sum += node->inc*(node->end - node->begin + 1);    gTreeNodes[left_child].inc += node->inc;    gTreeNodes[right_child].inc += node->inc;    node->inc = 0;}void BuildTree(int node_index, int beg, int end){    TreeNode* node = gTreeNodes + node_index;    node->inc = node->sum = 0;    node->begin = beg;    node->end = end;    if (beg ==  end){        node->sum = gNumber[beg];        return;    }    int mid = (beg + end) / 2, left_child = 2 * node_index + 1, right_child = 2 * node_index + 2;    BuildTree(left_child, beg, mid);    BuildTree(right_child, mid + 1, end);    //自底向上更新    PushUp(node_index);}void Add(int node_index, int beg, int end, long long c){    TreeNode* node = gTreeNodes + node_index;    int left_child = 2 * node_index + 1, right_child = 2 * node_index + 2, mid = (node->begin + node->end) / 2;    if (node->begin > end || node->end < beg){        return;    }    //如果当前结点被查询区间全部覆盖，则不向下传递，直接将inc值增加    if (node->begin >= beg && node->end <= end){        node->inc += c;        return;    }    //如果节点不能被查询区间全部覆盖，则需要分裂节点向下传递，此时的sum值需要增加（inc * 两区间重合的长度）    //而同时 inc 值保持不变    node->sum += (Interval(node->begin, node->end, beg, end) * c);    int end1 = MIN(end, mid);    int beg1 = MAX(beg, mid + 1);    Add(left_child, beg, end1, c);    Add(right_child, beg1, end, c);}long long QuerySum(int node_index, int beg, int end){    TreeNode* node = gTreeNodes + node_index;//    printf("node %d's sum = %d\n", node_index, gTreeNodes[node_index].sum);//    printf("node->beg = %d, node->end = %d, beg = %d, end = %d\n", node->begin, node->end, beg, end);    int left_child = 2 * node_index + 1, right_child = 2 * node_index + 2, mid = (node->begin + node->end) / 2;    long long sum = 0;    if (node->begin > end || node->end < beg){        return sum;    }    if (node->begin >= beg && node->end <= end){        sum  += (node->sum + node->inc*(node->end - node->begin + 1));    }    else{        //向下分裂的更新操作        PushDown(node_index);        int end1 = MIN(end, mid);        int beg1 = MAX(beg, mid + 1);        long long sum_left = QuerySum(left_child, beg, end1);        long long sum_right = QuerySum(right_child, beg1, end);        sum += (sum_left + sum_right);    }    return sum;}int main(){    scanf("%d %d", &gNumCount, &gQueryCount);    for (int i = 0; i < gNumCount; i++){        scanf("%d", gNumber + i);    }    BuildTree(0, 0, gNumCount - 1);    char op;    int a, b;    long long c;    long long result;    for (int i = 0; i < gQueryCount; i++){        getchar();        scanf("%c", &op);        if (op == 'C'){            scanf("%d %d %lld", &a, &b, &c);            Add(0, a- 1, b-1, c);            /*            for (int k = 0; k < 27; k++){                printf("node[%d]'s sum = %lld, inc = %lld\n", k, gTreeNodes[k].sum, gTreeNodes[k].inc);            }            */        }        else if (op == 'Q'){            scanf("%d %d", &a, &b);            result = QuerySum(0, a-1, b-1);            printf("%lld\n", result);        }    }    return 0;}