我们知道树状数组是支持单点修改和区间查询的,但是如何进行区间修改呢?

直接进行多次单点修改的话,效率是很低的。

对于这个问题,我们可以采用差分的方式去解决

题目:POJ3468

#include <algorithm>
#include <cstdio>
#include <iostream>
#pragma GCC optimize("O3")
using namespace std;
#define MAXN 100005
typedef long long ll;

ll sum1[MAXN], sum2[MAXN];
int n, q;

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

void add(ll *bit, int i, ll x)
{
    while (i <= n)
    {
        bit[i] += x;
        i += lowbit(i);
    }
}

ll sum(ll *bit, int i)
{
    ll ans = 0;
    while (i > 0)
    {
        ans += bit[i];
        i -= lowbit(i);
    }
    return ans;
}
void modify(ll tmpa, ll tmpb, ll tmpc)
{
    add(sum1, tmpa, tmpc);
    add(sum1, tmpb + 1, -tmpc);
    add(sum2, tmpa, (tmpa)*tmpc);
    add(sum2, tmpb + 1, -(tmpb + 1) * tmpc);
}

ll ask(int p)
{
    return (p + 1) * sum(sum1, p) - sum(sum2, p);
}
int main()
{
    scanf("%d%d", &n, &q);
    ll tmpa;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%lld", &tmpa);
        //add(sum1, i, tmpa);
        modify(i, i, tmpa);
    }

    ll tmpb, tmpc;
    char cmd;
    while (q--)
    {
        scanf("%s", &cmd);
        if (cmd == 'C')
        {
            scanf("%lld%lld%lld", &tmpa, &tmpb, &tmpc);
            modify(tmpa, tmpb, tmpc);
            /*
            add(sum1, tmpa, -tmpc*(tmpa-1));
            add(sum2, tmpa, tmpc);
            add(sum1, tmpb+1, tmpc*tmpb);
            add(sum2, tmpb+1, -tmpc);
            */
        }
        else
        {
            scanf("%lld%lld", &tmpa, &tmpb);
            /*
            ll ans = sum(sum1, tmpb) + sum(sum2, tmpb)*tmpb;
            ans -= sum(sum1, tmpa-1) + sum(sum2, tmpa-1)*(tmpa-1);
            */

            ll ans = ask(tmpb) - ask(tmpa - 1);
            // ans -= (tmpa)*sum(sum1, tmpa-1)-sum(sum2, tmpa-1);

            printf("%lld\n", ans);
        }
    }
}

转载请注明来源:https://www.longjin666.top/?p=1210

你也可能喜欢

发表评论