# [BZOJ 3155] Preprefix sum

## Description

1. Modify i x：把$$a_i$$改成$$x$$
2. Query i：查询$$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 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() {
for (int i = 1; i <= n; ++i) c[i] = read(), a.update(i, c[i]), b.update(i, 1LL * i * c[i]);
while (m--) {
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

(0)
(0)

0条