AcWing 243. A simple integer problem 2 (tree array interval modification interval query)

The question ：

This problem requires the use of tree array Interval modification and Interval query .

Ideas ：

stay Last question in , We maintain an original array with a tree array a The differential array of b, For every instruction “C l r d”, hold b[i] add d, And then b[r+1] subtract d.

What has been discussed is ：b Of 1~x The prefix and b[1~x] After these instructions ,a[x] Increased value .

that a The prefix and of the sequence a[1~x] The overall value added is

The above formula can be further rewritten into ：

Derivation process ：

Therefore, in this problem, we can consider adding a tree array , For maintenance i*b[i] And , The above formula can be calculated directly .

To be specific , We build two tree arrays , Respectively c1, c2, Initially, all values are 0, For every instruction “C l r d”, Perform four operations ：

• ① c1 Of l Position plus d.
• ② c1 Of r+1 Position subtraction d.
• ③ c2 Of l Position plus l*d.
• ④ c2 Of r+1 Position subtraction (r+1)*d.

For every instruction “Q l r”, We can directly apply the formula derived above to calculate .

This problem brings us a kind of thought , Separate items that contain multiple variables , Make different variables in the formula independent of each other , This idea is very important .

Time complexity ：

O(mlogn)

Code ：

#include<bits/stdc++.h>

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

int read() {// Fast reading 
    int x=0,f=1; char c=getchar();
    while(c<'0' || c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
    return x*f;
}

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

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

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

signed main()
{
        cin>>n>>m;
        for(int i=1;i<=n;++i)
        {
                a[i] = read();
                add(i, a[i]-a[i-1], c1), add(i, i*(a[i]-a[i-1]), c2);
        }
        while(m--)
        {
                char op[2];
                int l, r, d;
                scanf("%s", op);
                l = read(), r = read();
                if(*op=='C')
                {
                        d = read();
                        add(l, d, c1), add(l, l*d, c2);
                        add(r+1, -d, c1), add(r+1, -(r+1)*d, c2);
                }
                else
                {
                        printf("%lld\n", (r+1)*(ask(c1, r)) - ask(c2, r) - l*(ask(c1, l-1)) + ask(c2, l-1));
                }
        }
        return 0;
}