AcWing 243. 一个简单的整数问题2 （树状数组）打卡

题目：https://www.acwing.com/problem/content/244/

题意：区间加，区间查询

思路：我们把原先那个差分数组分解一下

∑i=1x∑j=1ib[j]=∑i=1x(x−i+1)×b[i]=(x+1)∑i=1xb[i]−∑i=1xi×b[i]

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define lowbit(x) x&(-x)

const int N=2e5;

ll c1[N],c2[N],n,m,a[N];

ll add(ll x,ll y)

{

    for(ll i=x;i<=n;i+=lowbit(i))

    {

        c1[i]+=y;

        c2[i]+=x*y;

    }

}

ll ask(ll x)

{

    ll ans=;

    for(ll i=x;i;i-=lowbit(i))

        ans+=(x+)*c1[i]-c2[i];

    return ans;

}

int main()

{

    scanf("%lld%lld\n",&n,&m);

    for(ll i=;i<=n;i++)

    {

        scanf("%lld",&a[i]);

        add(i,a[i]-a[i-]);

    }

    getchar();

    while(m--)

    {

        char ch=getchar();

        if (ch=='Q')

        {

            ll x,y;

            scanf("%lld%lld\n",&x,&y);

            cout<<ask(y)-ask(x-)<<endl;

        }

        if (ch=='C')

        {

            ll x,y,d;

            scanf("%lld%lld%lld\n",&x,&y,&d);

            add(x,d);

            add(y+,-d);

        }

    }

    return ;

}

AcWing 243. 一个简单的整数问题2 （树状数组）打卡的相关教程结束。