树状数组 && 线段树

树状数组

支持单点修改

#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]维护序列的题解

上一篇：NOIP2014D2T2寻找道路（Spfa）

下一篇：飞行员配对方案问题（匈牙利算法+sort）

---

线段树 树状数组 模板