树状数组——一个简单的整数问题

传送门：242. 一个简单的整数问题 - AcWing题库

朴素思路：

首先最简单的一个思路就是维护给出的序列a的前缀和，然后在根据给出的 l,r,x;

在r-l范围内的每一个数都走一次增加操作，每一次这样操作的最差的时间复杂度是O(NlogN),操作有100000次，10^10次方差不多，铁超时。

正确思路：

由题目可以发现每一次要输出的询问都是单点查询，并没有直接涉及修改完之后前缀和的内容，

到这里我们可以将做法从“维护a数列的具体数值”转变为“维护增加指令带的影响”。

比如对于区间增加的操作可以用一个初始全0的数列去维护：

c (l,r,x)

      l       r+1

0 0 x 0 0 -x

利用前缀和的性质，在l出加上一个x再在r+1处减去一个x就相当于在区间[l,r]都加上了x

反映到序列a上就是序列a对应位置的变化，如要查询x处的数值，就可以用原序列a[x]的值加上c[x]处就是经过一系列增加操作后的x处的数值。

c[x]在这里的具体含义是一系列的增加操作对位置为x的数的变化。 

代码：

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=1e5+10;
int c[N];
int a[N];
int n,m;
int lowbit(int x)//作用：得到x的二进制下最小的2的次幂
{
    return x&(-x);
}
void add(int x,int y)
{
    for(;x<=n;x+=lowbit(x)) c[x]+=y;
}
int ask(int x)
{
    int ans=a[x];
    for(;x;x-=lowbit(x)) ans+=c[x];
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
 
    while(m--)
    {
        char op;
        cin>>op;
        if(op=='Q')
        {
            int x;
            scanf("%d",&x);
            printf("%d\n",ask(x));
        }else
        {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            add(l,x);
            add(r+1,-x);
        }
    }
    return 0;
}