1. 首页
2. 线段树
3. 本页

Poj3468 A Simple Problem with Integers (成段更新)

题目链接:点我～～

线段树功能:update:成段增减 query:区间求和

不再是替换，而是增减，修改对应标记的增减～

//#include <bits/stdc++.h>
#include<cstdio>
#include<iostream>
using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

typedef long long LL;
const int MAXN = 100550;

LL sum[MAXN << 2];
LL col[MAXN << 2];

void pushup(int rt) {
	sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void pushdown(int rt, int s) {
	if (col[rt]) {
		col[rt << 1] += col[rt];
		col[rt << 1 | 1] += col[rt];
		sum[rt << 1] += (s - (s >> 1)) * col[rt];
		sum[rt << 1 | 1] += (s >> 1) * col[rt];
		col[rt] = 0;
	}
}

void build(int l, int r, int rt) {
	col[rt] = 0;
	if (l == r) {
		scanf("%lld", &sum[rt]);
		return;
	}
	int m = (l + r) >> 1;
	build(lson);
	build(rson);
	pushup(rt);
}

void update(int L, int R, int ans, int l, int r, int rt) {
	if (L <= l && r <= R) {
		col[rt] += ans;
		sum[rt] += ans * (r - l + 1);
		return;
	}
	pushdown(rt, r - l + 1);
	int m = (l + r) >> 1;
	if (L <= m) {
		update(L, R, ans, lson);
	}
	if (R > m) {
		update(L, R, ans, rson);
	}
	pushup(rt);
}

LL query(int L, int R, int l, int r, int rt) {
	if (L <= l && r <= R) {
		return sum[rt];
	}
	pushdown(rt, r - l + 1);
	LL res = 0;
	int m = (l + r) >> 1;
	if (L <= m) {
		res += query(L, R, lson);
	}
	if (R > m) {
		res += query(L, R, rson);
	}
	return res;
}

int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	build(1, n, 1);
	char tmp;
	int a, b, c;
	while (q--) {
		cin >> tmp;
		if (tmp == 'C') {
			scanf("%d%d%d", &a, &b, &c);
			update(a, b, c, 1, n, 1);
		} else {
			scanf("%d%d", &a, &b);
			printf("%lld\n", query(a, b, 1, n, 1));
		}
	}

	return 0;
}