AcWing 242. A simple integer problem (tree array + difference)

Pre knowledge ：

Tree array 、 Prefix sum and difference .

The question ：

Ideas ：

The instructions of this question are “ The interval increases ”,“ Single point query ”.

These two instructions are Naked difference What can be accomplished , The former O(1), the latter O(n), But according to the title , Element number n And the number of inquiries m The data range of is 1e5, If you use naked difference , complete m Single point query requires O(n^2), Obviously illegal , We should abandon .

The correct approach ： Tree array + Difference , Or say Use the difference group to build a tree array .

The basic instruction of tree array is ：“ Single point increase ”,“ Interval query ”, When combined with differential array, it can be realized “ The interval increases ”,“ Single point query ” 了 ！

（ Single point increase of the difference array , Corresponding to the original array interval increase , Before the differential array query i Item prefix and corresponding original array query a[i]）

Time complexity ：

O(mlogn)

Code ：

/* Save the difference group into the tree array , The original array is the prefix of the tree array and , Turn the problem into a tree array ,
 Original array No x The number is the tree array 1~x And */
#include<bits/stdc++.h>

using namespace std;
#define int long long
const int N = 1e5+10;
int n, m;
int a[N], c[N];

int lowbit(int x) {return x & (-x);}

int ask(int x){
        int ans = 0;
        while(x) {ans+=c[x], x-=lowbit(x);}
        return ans;
}

void add(int x, int y)
{
        for(; x<=n; x+=lowbit(x)) c[x]+=y;
}

signed main()
{
        cin>>n>>m;
        for(int i=1;i<=n;++i)
        {
                scanf("%lld",&a[i]);
                add(i, a[i]-a[i-1]);// use add Construct a differential tree array 
        }

        while(m--)
        {
                char op[2];
                int l, r, d, x;
                scanf("%s",op);
                if(*op=='C') {
                        scanf("%lld%lld%lld", &l, &r, &d);
                        add(l, d), add(r+1, -d);// use O(1) The complexity of interval modification 
                }
                else{
                        scanf("%lld", &x);
                        printf("%lld\n", ask(x));
                }
        }

        return 0;
}