526互联

POJ3468 A Simple Problem with Integers

发布时间 2023-07-12 10:07:51作者: FlyingLight

A Simple Problem with Integers

题目链接：A Simple Problem with Integers

题意

给定\(N\)个数，可以选择\([l,r]\)，让下标在区间内的值都增加一定值，或者输出下标在区间内元素的和。

思路

可以用带懒标记的线段树写，但是代码太长，不利于编写。这里有一个利用差分借助树状数组实现的写法，非常巧妙，可以实现区间修改（受限于差分的性质，不能实现区间赋值，只能区间加值），区间查询。

令原数组为\(a[]\),差分数组为\(c[]\)，令\(b[i]=(i-1)c[i]\)则：

\(\sum_{i=1}^{n}a[i] = c[1]+(c[1]+c[2])+...+(c[1]+c[2]+...+c[n-1]+c[n])=\sum_{i=1}^{n}(n-i+1)c[i]\)

在这一步，\((n-i+1)c[i]\)不能直接用树状数组操作，因为式子中的\(n\)不是提议中的\(n\)，而是每次查询时使用的，导致这个式子在赋值时无法操作，还需要进一步操作：

\(\sum_{i=1}^{n}(n-i+1)c[i]=n\sum_{i=1}^{n}c[i]-\sum_{i=1}^{n}(i-1)c[i]\)=\(n\sum_{i=1}^{n}c[i]-\sum_{i=1}^{n}b[i]\)

这样就利用\(c[i]\)和\(b[i]\)创建两个树状数组来对区间操作。

代码

#include <cstdio>
#include <iostream>
using namespace std;
#define LL long long

const int maxn = 1e5 + 5;
int a[maxn], n;
LL b[maxn], c[maxn];

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

void add(int x, LL d) {
    LL tmp = x;
    while (x <= n) {
        c[x] += d;
        b[x] += (tmp - 1) * d;
        x += lowbit(x);
    }
}

LL query(int x) {
    LL sum = 0, tmp = x;
    while (x > 0) {
        sum += tmp * c[x] - b[x];
        x -= lowbit(x);
    }
    return sum;
}

void sol() {
    int q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        add(i, a[i] - a[i - 1]);
    }
    for (int i = 1; i <= q; ++i) {
        char op;
        getchar();
        cin >> op;
        int x, y;
        cin >> x >> y;
        if (op == 'Q')
            cout << query(y) - query(x - 1) << endl;
        else {
            int d;
            cin >> d;
            add(x, d);
            add(y + 1, -d);
        }
    }
}

int main() {
    sol();
    return 0;
}