前缀和(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\),有两种操作:
Modify i x
:把\(a_i\)改成\(x\);Query i
:查询\(SS_i\)第一行给出两个整数\(N,M\)。分别表示序列长度和操作个数
接下来一行有\(N\)个数,即给定的序列\(a_1,a_2,\dots,a_n\)
接下来\(M\)行,每行对应一个操作,格式见题目描述
对于每个询问操作,输出一行,表示所询问的\(SS_i\)的值。
5 3
1 2 3 4 5
Query 5
Modify 3 2
Query 5
35
32
\(1\le N,M\le100000\),且在任意时刻 \(0\le A_i\le100000\)
\[ \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} \]
#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;
}
原文:https://www.cnblogs.com/fly-in-milkyway/p/10366904.html