线段树-JZTXT

线段树 vs 树状数组

代码长度：树状数组段
可扩展性：线段树强，二树状数组仅局限于和的处理
思维难度：线段树简单比如区查区改树状数组还要打开多项式搞

延迟标记：为了处理当修改区间是\([1,n]\)时所有节点都要被修改一遍的情况

如果修改区间覆盖当前区间，那么这颗子树之内所有节点都要修改，干脆在根打个标记，延迟更新
等到出现 1.修改区间未覆盖当前区间（不能省） 2.需要查询两种情况时下传标记

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std ;

typedef long long ll ;
const int N = 100010 ;

int n, q ;
int a[N] ;

struct node {
	int l, r ; ll v ;
	int lt ; // lazy tag 
	#define ls(x) tr[x].l
	#define rs(x) tr[x].r
	#define v(x) tr[x].v
	#define lt(x) tr[x].lt
} tr[N * 4] ;

void build(int x, int l, int r) {
	ls(x) = l, rs(x) = r ; lt(x) = 0 ;
	if (l == r) {
		v(x) = a[l] ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	build(x * 2, l, mid) ;
	build(x * 2 + 1, mid + 1, r) ;
	v(x) = v(x * 2) + v(x * 2 + 1) ;
} 

int spread(int x) {
	if (lt(x) != 0) {
		lt(x * 2) += lt(x) ;
		lt(x * 2 + 1) += lt(x) ;
		v(x * 2) += lt(x) * (rs(x * 2) - ls(x * 2) + 1) ;
		v(x * 2 + 1) += lt(x) * (rs(x * 2 + 1) - ls(x * 2 + 1) + 1) ;
		lt(x) = 0 ;
	}
}

void modify(int x, int l, int r, int c) {
	if (l <= ls(x) && rs(x) <= r) {
		v(x) += c * (rs(x) - ls(x) + 1) ;
		lt(x) += c ;
		return ;
	}
	spread(x) ;
	int mid = (ls(x) + rs(x)) >> 1 ;
	if (l <= mid) modify(x * 2, l, r, c) ;
	if (mid + 1 <= r) modify(x * 2 + 1, l, r, c) ;
	v(x) = v(x * 2) + v(x * 2 + 1) ;
}

ll query(int x, int l, int r) {
	spread(x) ;
	if (l <= ls(x) && rs(x) <= r) return v(x) ;
	ll ans = 0 ; int mid = (ls(x) + rs(x)) >> 1 ;
	if (l <= mid) ans += query(x * 2, l, r) ;
	if (mid + 1 <= r) ans += query(x * 2 + 1, l, r) ;
	return ans ;
} 

char get() {
	char t = getchar() ;
	while (!isalpha(t)) t = getchar() ;
	return t ;
}

int main() {
	scanf("%d%d", &n, &q) ;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]) ;
	build(1, 1, n) ;
	while (q--) {
		char op = get() ; 
		if (op == 'C') {
			int l, r, c ; scanf("%d%d%d", &l, &r, &c) ;
			modify(1, l, r, c) ;
		} else {
			int l, r ; scanf("%d%d", &l, &r) ;
			printf("%lld\n", query(1, l, r)) ;
		}
	}
}