[BZOJ 3155] Preprefix sum

Description

前缀和(prefix sum)\(S_i=\sum_{k=1}^i a_i\)。

前前缀和(preprefix sum) 则把\(S_i\)作为原序列再进行前缀和。记再次求得前缀和第\(i\)个是\(SS_i\)

给一个长度\(n\)的序列\(a_1, a_2, \cdots, a_n\)，有两种操作：

1. Modify i x：把\(a_i\)改成\(x\)；
2. Query i：查询\(SS_i\)

Input

第一行给出两个整数\(N,M\)。分别表示序列长度和操作个数
接下来一行有\(N\)个数，即给定的序列\(a_1,a_2,\dots,a_n\)
接下来\(M\)行，每行对应一个操作，格式见题目描述

Output

对于每个询问操作，输出一行，表示所询问的\(SS_i\)的值。

Sample Input

5 3
1 2 3 4 5
Query 5
Modify 3 2
Query 5

Sample Output

35
32

HINT

\(1\le N,M\le100000\)，且在任意时刻 \(0\le A_i\le100000\)

Solution

\[ \begin{eqnarray} SS_i&=&\sum_{j=1}^{i}\sum_{k=1}^{j}a_k\&=&\sum_{j=1}^{i}(i-j+1)\times a_j\&=&(i+1)\times\sum_{j=1}^{i}a_j-\sum_{j=1}^{i}j\times a_j \end{eqnarray} \]

Code

#include <cstdio>
#include <algorithm>

const int N = 100005;
char op[10]; int n, m, x, y, c[N];

struct BIT {
    long long sum[N];
    void update(int x, long long y) {
        while (x <= n) sum[x] += y, x += x & (-x);
    }
    long long query(int x) {
        long long res = 0;
        while (x) res += sum[x], x -= x & (-x);
        return res;
    }
} a, b;

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return x;
}
int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; ++i) c[i] = read(), a.update(i, c[i]), b.update(i, 1LL * i * c[i]);
    while (m--) {
        scanf("%s", op), x = read();
        if (op[0] == 'Q') printf("%lld\n", (x + 1) * a.query(x) - b.query(x));
        else y = read(), a.update(x, y - c[x]), b.update(x, 1LL * x * (y - c[x])), c[x] = y;
    }
    return 0;
}

[BZOJ 3155] Preprefix sum

原文：https://www.cnblogs.com/fly-in-milkyway/p/10366904.html