树状数组
支持单点修改
#include <cstdio> using namespace std; int n, m; int a[500001], c[500001]; int lowbit(int x) int sum(int x) return ans; } void add(int x, int d) } int main() for(i = 1; i <= m; i++) return 0; }View Code
支持区间修改
#include <cstdio> #include <iostream> using namespace std; int n, m; long long c0[100001], c1[100001], a[100001]; long long lowbit(int x) long long sum(long long *c, int x) return ans; } void add(long long *c, int x, int d) } int main() for(i = 1; i <= m; i++) else } return 0; }View Code
线段树
支持区间修改
add[o]表示节点o的lazy标记，且节点o已经修改完
#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define root 1, 1, N #define ls o << 1, l, m #define rs o << 1 | 1, m + 1, r int L, R; long long add[1500005], mul[1500005], c[1500005], P; inline int read() while(isdigit(ch)) return x * f; } inline void pushup(int o) inline void build(int o, int l, int r) int m = (l + r) >> 1; build(ls); build(rs); pushup(o); } inline void pushdown(int o, int m) inline void update(int f, int d, int o, int l, int r) else return; } pushdown(o, r l + 1); int m = (l + r) >> 1; if(L <= m) update(f, d, ls); if(m < R) update(f, d, rs); pushup(o); } inline long long query(int o, int l, int r) int main() else } return 0; }View Code
ps:有意思的是这个代码还是[AHOI2009]维护序列的题解
上一篇：【割点】【割边】tarjan
下一篇：Cannot resolve org.springframework.boot:spring-boot-starter-parent:2.4.3
模板 线段树 树状数组
