【セグメントツリーの複雑な状態維持】Ryuji doesn't want to study
2418 ワード
https://nanti.jisuanke.com/t/31460
注意問い合わせ時のマージ操作
コード:
tree[rt].ans = tree[rt << 1].ans + tree[rt << 1 | 1].ans + tree[rt << 1].sum * tree[rt << 1 | 1].len;
注意問い合わせ時のマージ操作
コード:
#include
#include
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = (int)1e5 + 5;
typedef long long ll;
using namespace std;
int n, q;
ll arr[maxn];
struct Tree {
ll sum, ans, len;
} tree[maxn << 2];
void pushup(int rt) {
tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
tree[rt].ans = tree[rt << 1].ans + tree[rt << 1 | 1].ans + tree[rt << 1].sum * tree[rt << 1 | 1].len;
}
void build(int l, int r, int rt) {
tree[rt].len = r - l + 1;
if (l == r) {
tree[rt].sum = tree[rt].ans = arr[l];
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushup(rt);
}
void update(int p, ll val, int l, int r, int rt) {
if (l == r) {
tree[rt].ans = tree[rt].sum = val;
return;
}
int m = (l + r) >> 1;
if (p <= m) {
update(p, val, lson);
}
else {
update(p, val, rson);
}
pushup(rt);
}
ll _query(int L, int R, int l, int r, int rt) {
if (L <= l && R >= r) {
return tree[rt].sum;
}
int m = (l + r) >> 1;
ll res = 0;
if (L <= m) {
res += _query(L, R, lson);
}
if (R > m) {
res += _query(L, R, rson);
}
return res;
}
ll query(int L, int R, int l, int r, int rt) {
if (L <= l && R >= r) {
return tree[rt].ans;
}
int m = (l + r) >> 1;
if (L <= m && R > m) {
return query(L, m, lson) + query(m + 1, R, rson) + _query(L, m, lson) * (R - m);
}
else if (L <= m) {
return query(L, R, lson);
}
else {
return query(L, R, rson);
}
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%lld", &arr[i]);
}
build(1, n, 1);
while (q--) {
int op, a, b;
scanf("%d%d%d", &op, &a, &b);
if (op == 1) {
printf("%lld
", query(a, b, 1, n, 1));
}
else {
update(a, b, 1, n, 1);
}
}
}