C02【模板】线段树+懒标记 Luogu P3372 线段树——信息学竞赛算法_哔哩哔哩_bilibili

算法讲解110【扩展】线段树专题1-线段树原理和代码详解_哔哩哔哩_bilibili

线段树的作用

能够在O(logn)时间内 范围的维护,修改区间的某个状态

线段树的实现原理

n个数, 设m为区间的中点, 1~n区间的状态存在i位置, 1~m存在2 * i位置,m + 1~ n区间的状态存在2*i + 1的位置

存的数组开为4*n即可够用

代码实现(以区间和为例)  (自己写的以后可能会优化)

初始化建立

void build(int p, int l, int r) {  //l~r区间的状态存到p位置if(l == r) {sum[p] = a[l];return sum[p];}int m = l + r >> 1;int lc = p << 1, rc = p << 1 | 1;sum[p] = build( lc, l, m);sum[p] += build( rc, m + 1, r);}

点修改

auto pl = [&](auto self, int p, int l, int r, int t, int x) -> void{//t位置的数加上xif(l == r && l == t){sum[p] += x;return;}int lc = 2 * p, rc = 2 * p + 1;if((l + r >> 1) >= t)  self(self, lc, l ,l + r >> 1, t, x);else self(self, rc, (l + r >> 1) + 1, r, t ,x);sum[p] = sum[lc] + sum[rc];};

区间修改 (懒标记)

auto pl = [&](auto self, int p, int l, int r, int ll, int rr, int x) -> void{if(l >= ll && r <= rr){add[p] += x;return;}int m = l + r >> 1;/*写的时候丢了,debug很长时间*/sum[p] += (min(rr,r) - max(l,ll) + 1) * x; int lc = 2 * p, rc = 2 * p + 1;if(m >= ll) self(self, lc, l, m, ll, rr, x);if(rr >= m + 1) self(self, rc,m + 1, r, ll, rr, x);};

区间查询 (懒标记)

auto cha = [&](auto self, int p, int l, int r, int ll,int rr) -> void{int m = l + r >> 1;if(l >= ll && r <= rr){ans += sum[p] + add[p] * (r - l + 1);return;}int lc = 2 * p, rc = 2 * p + 1;add[lc] += add[p], add[rc] += add[p];/*丢了*/sum[p] += add[p] * (r - l + 1);add[p] = 0;if(ll <= m)  self(self, lc, l ,m, ll, rr);if(rr >= m + 1) self(self, rc, m + 1, r, ll, rr);};

题目 : 洛谷 P3374 P3372 F-小红的数组操作_牛客周赛 Round 57 (nowcoder.com)