参考博客:
Mahr
Liangyj
线段树:是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,实际应用时一般还要开4N的数组以免越界,因此有时需要离散化让空间压缩。
建树操作
1 | struct node |
懒标记(区间求和)
1 | void lazy(int p) |
区间修改(加/减)
1 | void change(int p,int x,int y,int z) |
区间求和
1 | long long sum(int p,int x,int y) |
单点查询
1 | long long single_sum(int p,int x) |
单点修改(加/减)
1 | void single_change (int p,int x,int z) |
区间修改(更改数值)
1 | void lazy(int p) |
区间最大值,最小值
1 | const int maxn = 200000+200; |