242. 一个简单的整数问题（树状数组）

àì夳堔傛蜴生んèń 2021-11-11 13:10 235阅读 0赞

题目链接：[https://www.acwing.com/problem/content/248/][https_www.acwing.com_problem_content_248]  
给定长度为N的数列A，然后输入M行操作指令。

第一类指令形如“C l r d”，表示把数列中第l~r个数都加d。

第二类指令形如“Q X”，表示询问数列中第x个数的值。

对于每个询问，输出一个整数表示答案。  
输入格式

第一行包含两个整数N和M。

第二行包含N个整数A\[i\]。

接下来M行表示M条指令，每条指令的格式如题目描述所示。  
输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。  
数据范围

1≤N,M≤105  
,  
|d|≤10000,  
|A\[i\]|≤1000000000

输入样例：

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

输出样例：

4  
1  
2  
5

分析：  
明确两点。这个题目要干什么，两个操作，1是区间增加；2是单点查询。  
可是我们的树状数组只支持单点增加。所以，我们势必要把区间增加改成单点操作。  
很容易想到差分序列。回想差分序列是对单点的改变却能引起整个区间的改变。  
故我们可以新建一个数组d。起初为全0。对于每条指令C l r b。我们可以进行如下操作：  
d\[l\]+=b;  
d\[r +1\] -= b;  
执行上面两个指令后，我们来考虑一下d数组的前缀和的情况：  
1，对于1<= x< l.。前缀和不变。  
2，对于l <= x<= r.前缀和增加了d。  
3，对于r<= x<= N,前缀和不变。

我们发现，d数组的前缀和d\[1~x\]就反映了指令C l r d. 对于a\[x\]产生的影响。

所以，我们用树状数组维护d数组的前缀和。就可得到下标为x的改变情况。  
故，a\[x\] + sum\[x\] 就是a改变后的值

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    ll C[100100];
    ll a[100100];
    int N,M;
    
    int lowbit(int x)
    {
        return x & (-x);
    }
    void add(int x,int v)
    {
        for(int i = x; i <= N; i+= lowbit(i))
        {
            C[i] += v;
        }
    }
    ll ask(int x)
    {
        ll sum = 0;
        while(x > 0)
        {
            sum += C[x]; x -= lowbit(x);
        }
        return sum;
    }
    
    int main()
    {
        scanf("%d%d",&N,&M);
        for(int i = 1; i <= N;i ++)
        {
            scanf("%lld",&a[i]);
        }
        while(M --)
        {
            char str[2];
            scanf("%s",str);
            if(str[0] == 'Q')
            {
                int x; scanf("%d",&x);
                ll sum = ask(x);
                //printf("sum = %lld a[x] = %d\n",sum,a[x]);
                printf("%lld\n",(ll)sum + a[x]);
            }
            else
            {
                int l,r,x;
                scanf("%d%d%d",&l,&r,&x);
                add(l,x);
                add(r + 1,-x);
            }
        }
    }

[https_www.acwing.com_problem_content_248]: https://www.acwing.com/problem/content/248/