C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 + 10;
typedef long long LL;
int n, m, a[M], N;
LL tree[M << 1], mark[M << 1];
void build()
{
N = n - 1;
for (int i = 1; i <= n; i ++ ) tree[i + N] = a[i];
for (int i = N; i; i -- ) tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
void change(int l, int r, int d)
{
int len = 1, cntl = 0, cntr = 0;
for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1, len <<= 1)
{
tree[l] += cntl * d, tree[r] += cntr * d;
if (!(l & 1)) tree[l ^ 1] += len * d, mark[l ^ 1] += d, cntl += len;
if (r & 1) tree[r ^ 1] += len * d, mark[r ^ 1] += d, cntr += len;
}
for (; l; l >>= 1, r >>= 1) tree[l] += cntl * d, tree[r] += cntr * d;
}
LL query(int l, int r)
{
LL ans = 0, len = 1, cntl = 0, cntr = 0;
for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1, len <<= 1)
{
ans += cntl * mark[l] + cntr * mark[r];
if (~l & 1) ans += tree[l ^ 1], cntl += len;
if (r & 1) ans += tree[r ^ 1], cntr += len;
}
for (; l; l >>= 1, r >>= 1)
ans += cntl * mark[l] + cntr * mark[r];
return ans;
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
build();
while (m -- )
{
char x[2];
int l, r, d;
scanf("%s %d %d", x, &l, &r);
if (x[0] == 'C')
{
scanf("%d", &d);
change(l, r, d);
}
else printf("%lld\n", query(l, r));
}
}