F - A Simple Problem with Integers

        这个题也是二叉搜索树的应用,但是考虑到数据是一个区间更新而不是单点更新,所以每个点都更新的话计算量太大会导致TLE,网上搜索之后看到基本上是使用“lazy”思想。所以更改几行关键代码就能AC了。

         下面说下我对lazy思想的理解:

        所谓"lazy",就是惰性的意思。当某个区间上很多的值都要更新的时候,我们会采取”lazy“来减少计算量。具体到这个题目我们来分析一下。首先,要在结构体中增加一个inc的字段来保存这个区间的增量更新,当从根节点往下更新的时候,如果遇到了一个完全处在我们需要更新的节点里面的时候,我们就把下面这个区间段所有要更新的值全都加在这个区间的inc字段中。然后不不继续往下更新了。这样就节省了往下的数据计算量。然后等下次查询的时候查到这个区间,我们就把查询区间段和这个区间段重合的那一部分乘上我们刚刚更新的inc的值,这样就达到了不更新子节点的值也能得到我们想要的结果并且还节约了大量计算次数的效果了。


Description

给出了一个序列,你需要处理如下两种询问。

"C a b c"表示给[a, b]区间中的值全部增加c (-10000 ≤ c ≤ 10000)。

"Q a b" 询问[a, b]区间中所有值的和。

Input

第一行包含两个整数N, Q。1 ≤ N,Q ≤ 100000.

第二行包含n个整数,表示初始的序列A (-1000000000 ≤ Ai ≤ 1000000000)。

接下来Q行询问,格式如题目描述。

Output

对于每一个Q开头的询问,你需要输出相应的答案,每个答案一行。

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15



下面是我的代码实现:


#include <iostream>
#include <cstdio>
using namespace std;
struct Node
{
    int left;
    int right;
    long long value, inc;
};
const int maxn=1000000;
Node treeNode[maxn];
int n, q;
char command[2];
int coma, comb, comc;
long long QueryAns=0;
void BuildTree(int index, int left, int right)
{
    ///新建树
    treeNode[index].left=left;
    treeNode[index].right=right;
    treeNode[index].value=0;
    treeNode[index].inc=0;
    if(left==right)
    {
        long long value;
        scanf("%lld", &value);
        treeNode[index].value=value;    //更新叶子节点
        return;
    }
    int mid=(left+right)>>1;
    BuildTree(index<<1,left,mid);
    BuildTree((index<<1)+1,mid+1,right);
    treeNode[index].value+=treeNode[index<<1].value+treeNode[(index<<1)+1].value;   //更新父节点
}
void Update(int left, int right, int value, int index)
{
   if(treeNode[index].left <= left && treeNode[index].right >= right)
    {
       treeNode[index].value += (right-left+1)*value;
       if(treeNode[index].left == left && treeNode[index].right == right)
            treeNode[index].inc += value;   //lazy思想,暂存,不继续更新
       else
        { //不是恰好符合的区间,继续更新
           int mid=(treeNode[index].left+treeNode[index].right)/2;
           if(right <= mid)Update(left,right,value,index*2);
           else if(left>mid)Update(left,right,value,index*2+1);
           else
           {
              Update(left,mid,value,2*index);
              Update(mid+1,right,value,2*index+1);
           }
        }
   }
}
void Query(int left, int right, int index)
{
   int mid=(treeNode[index].left+treeNode[index].right)/2;
   if(left == treeNode[index].left && right == treeNode[index].right)
    {QueryAns += treeNode[index].value;}
   else if(left>mid)
    {
        QueryAns += treeNode[index].inc*(right-left+1);     //暂存区有值就加上
        Query(left,right,2*index+1);
    }
   else if(right<=mid)
    {
        QueryAns += treeNode[index].inc*(right-left+1);
        Query(left,right,2*index);
    }
   else
    {
        QueryAns += treeNode[index].inc*(right-left+1);
        Query(left,mid,2*index);
        Query(mid+1,right,2*index+1);
    }
}
int main()
{
    while(scanf("%d%d", &n, &q)!=EOF && n && q)
    {
        BuildTree(1, 1, n);
        for(int i=1;i<=q;i++)
        {
            scanf("%s", &command);
            if(command[0]=='C')
            {
                if(coma>comb)swap(coma, comb);
                scanf("%d%d%d", &coma, &comb, &comc);
                Update(coma, comb, comc, 1);
            }
            if(command[0]=='Q')
            {
                QueryAns=0;
                scanf("%d%d", &coma, &comb);
                Query(coma, comb, 1);
                printf("%lld\n", QueryAns);
            }
        }
    }
    return 0;
}