我们知道树状数组是支持单点修改和区间查询的,但是如何进行区间修改呢?
直接进行多次单点修改的话,效率是很低的。
对于这个问题,我们可以采用差分的方式去解决
题目: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);
}
}
}