线段树 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)) ;
}
}
}
标签:rs,int,线段,tr,lt,include
From: https://www.cnblogs.com/lighthqg/p/17654565.html