线段树是一种二叉树，可视为树状数组的变种，最早出现在2001年，由程序竞赛选手发明。
此数据结构实际应用用途不大，但由于其程序易于实现而被广泛应用于程序竞赛当中。其用途是在查询一个指定区间内的信息，并可在同样的时间复杂度支持更新等操作。
线段树是一个平衡的二元树，所有叶子到根的距离最多只差1。令整个区间的长度为N，则其有N个叶节点，每个叶节点代表一个单位区间，每个内部结点代表的区间为其两个儿子代表区间的联集。
线段树所要提供的是查询一个区间利用完全二叉堆的性质来保存节点编号, 所以rt << 1是左子树的节点, rt << 1 | 1是右子树的节点在查询和成端更新操作中的L和R是指修改或者查询的区间
将子节点的值更新到父节点。
查询一个指定区间内的信息，并可在同样的时间复杂度支持更新等操作。
利用完全二叉堆的性质来保存节点编号, 所以rt << 1是左子树的节点, rt << 1 | 1是右子树的节点在查询和成端更新操作中的L和R是指修改或者查询的区间/* 对于区间求和 */void push_up(int rt) { tree = tree + tree;}/* 对于区间求最大值 */void push_up(int rt) { tree = max(tree, tree);}对于区间求和, 原子数组值需要加上lazy标记乘以子树所统计的区间长度。len为父节点统计的区间长度, 则len - (len >> 1)为左子树区间长度, len >> 1为右子树区间长度。
void push_down(int rt, int len) { tree += lazy * (len - (len >> 1)); lazy += lazy; tree += lazy * (len >> 1); lazy += lazy; lazy = 0;}对于区间求最大值, 子树的值不需要乘以长度, 所以不需要传递参数len。
void push_down(int rt) { tree += lazy; lazy += lazy; tree += lazy; lazy += lazy; lazy = 0;}新建一棵长度N的线段树。
#define lchild rt << 1, l, m#define rchild rt << 1 | 1, m + 1, rvoid build(int rt = 1, int l = 1, int r = N) { if (l == r) { std::cin >> tree; return; } int m = (l + r) >> 1; build(lchild); build(rchild); push_up(rt);}单点更新, 不需要用到lazy标记
#define lchild rt << 1, l, m#define rchild rt << 1 | 1, m + 1, rvoid update(int p, int delta, int rt = 1, int l = 1, int r = N) { if (l == r) { tree += delta; return; } int m = (l + r) >> 1; if (p <= m) update(p, delta, lchild); else update(p, delta, rchild); push_up(rt);}成段更新, 需要用到lazy标记来提高时间效率
#define lchild rt << 1, l, m#define rchild rt << 1 | 1, m + 1, rvoid update(int L, int R, int delta, int rt = 1, int l = 1, int r = N) { if (L <= l && r <= R) { tree += delta * (r - l + 1); lazy += delta; return; } if (lazy) push_down(rt, r - l + 1); int m = (l + r) >> 1; if (L <= m) update(L, R, delta, lchild); if (R > m) update(L, R, delta, rchild); push_up(rt);}#define lchild rt << 1, l, m#define rchild rt << 1 | 1, m + 1, rint query(int L, int R, int rt = 1, int l = 1, int r = N) { if (L <= l && r <= R) return tree; if (lazy) push_down(rt, r - l + 1); int m = (l + r) >> 1, ret = 0; if (L <= m) ret += query(L, R, lchild); if (R > m) ret += query(L, R, rchild); return ret;}#include <iostream>#include <cstdio>#include <cmath>#include <cstring>using namespace std;namespace SegTree { #define maxn 1000000 class SegmentTree { #define lson (o<<1) #define rson (o<<1|1) #define mid ((l+r)>>1) public : int addv, maxv, minv, sumv; int arr; int N; private:int _max(const int& _, const int& __) { return _>__?_:__; } private:int _min(const int& _, const int& __) { return _<__?_:__; } public : int pushup(int o) { minv = _min(minv, minv); maxv = _max(maxv, maxv); sumv = sumv + sumv; return 0; } public : int pushdown(int o, int l, int r) { if(addv == 0) return -1; addv += addv; addv += addv; minv += addv; minv += addv; maxv += addv; maxv += addv; sumv += addv * (mid-l+1); sumv += addv * (r-mid); addv = 0; } public : int Build(int o, int l, int r) { addv = 0; if(l == r) { maxv = arr;minv = arr;sumv = arr; return 0; } Build(lson, l, mid); Build(rson, mid+1, r); pushup(o); return 0; } public : int optadd(int o, int l, int r, int ql, int qr, int addval) { if(ql > r or qr < l) return 0; if(ql <= l and r <= qr) { addv += addval; sumv += addval * (r-l+1); return 0; } pushdown(o, l, r); optadd(lson, l, mid, ql, qr, addval); optadd(rson, mid+1, r, ql, qr, addval); pushup(o); } public : int query_sum(int o, int l, int r, int ql, int qr) { if(ql > r or qr < l) return 0; if(ql <= l and r <= qr) { return sumv; } pushdown(o, l, r); return query_sum(lson, l, mid, ql, qr) + query_sum(rson, mid+1, r, ql, qr); } public : int query_min(int o, int l, int r, int ql, int qr) { if(ql > r or qr < l) return 0; if(ql <= l and r <= qr) { return minv; } pushdown(o, l, r); return _min(query_min(lson, l, mid, ql, qr), query_min(rson, mid+1, r, ql, qr)); } public : int query_max(int o, int l, int r, int ql, int qr) { if(ql > r or qr < l) return 0; if(ql <= l and r <= qr) { return maxv; } pushdown(o, l, r); return _max(query_max(lson, l, mid, ql, qr), query_max(rson, mid+1, r, ql, qr)); } };} //End of SegmentTreeusing namespace SegTree;zkw线段树是一种自底向上的线段树，由清华大学的张昆玮提出。它相对于传统线段树的优势体现在减少了递归操作和增加了位运算等操作以减少常数。
http://dongxicheng.org/structure/segment-tree/
