树状数组的区间修改与查询

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

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

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

题目：POJ3468

代码语言：javascript复制

#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("%lldn", ans);
        }
    }
}

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

数组 效率

0 人点赞