1.　非递归线段树

1.1.　线段树

　　线段树用于维护一维空间内离散的点, 是计算几何中处理特例中的特例所用的数据结构.

1.2.　非递归线段树

　　回忆通常的线段树的实现: 递归, 自顶向下. 这也就导致了线段树常数大的缺点.

　　假如...我们能构造出一棵支持自底向上的线段树, 就可以实现非递归啦.

　　幸运的是, zkw神犇构造出了这样一棵区间大小与 $n$ 同阶的线段树, 于是称其为 zkw线段树.

　　zkw线段树是有必要学习的, 它的亮点不仅在于其常数小, 而且在于实现很简单.

1.3.　zkw线段树的基本结构

　　zkw线段树是一棵满二叉树.

　　它存储的区间范围为 $[0, M = 2^d)$ , 其中 $M \ge n+2$ .

　　$M$ 可以通过这行代码处理:  for (M = 1; M < n+2; M <<= 1);

　　由于它是满二叉树, 所以:

　　$x$ 的父亲为 $\lfloor \frac{x}{2}\rfloor$ .

　　$x$ 的左儿子为 $2x$ .

　　$x$ 的右儿子为 $2x+1$ .

1.4.　单点访问

　　$[1, M)$ 为非叶子节点.

　　$[M, M+M)$ 为叶子节点.

　　对于区间内一个点 $x$ , 我们可以在 $O(1)$ 访问其叶子节点 $x + M$ .

1.5.　区间访问

　　每一层最多只会访问两个节点.

　　将闭区间 $[L‘, _R‘]$ 转化为开区间 $(L, R)$ .

　　访问 $L, R$ 对应的叶子节点.

　　沿着父亲往上跳, 直接 $L$ 与 $R$ 相邻.

　　当 $L$ 为左儿子的时候, 访问其右儿子.

　　当 $R$ 为右儿子的时候, 访问其左儿子.

for (L = L-1+M, R = R+1+M; L^R^1; L >>= 1, R >>= 1) {
    if (!(L&1)) Visit(L^1);
    if (R&1) Visit(R^1);
    Pushup(x);
}

1.6.　初始建树

　　初始建树有两种方法: 递归, 非递归.

　　非递归:

for (int i = M+M-1; i >=1; i--)
    tr[i] = (i > M ? a[i-M] : tr[i<<1] + tr[i<<1|1]);

　　递归:

void Build(int x, int L, int R) {
    if (R < 1 || L > n) return;
    if (L == R) {tr[x] = a[L]; return; }
    int M = (L+R)>>1;
    Build(x, L, M);
    Build(x, M+1, R);
    tr[x] = tr[x<<1] + tr[x<<1|1];   
}

　　非递归建树的特点在于: ①非递归, 常数大; ②访问了所有的点.

　　递归建树的特点在于: ①递归, 常数小; ②访问了与 $[1, n]$ 有交集的区间.

　　因此, 如果每个节点维护的信息量比较大, 譬如说是一个线性基, 那么就用递归建树, 否则就非递归建树.

1.7.　遍历整棵树 (标记下传)

void Tsunami(int x, int L, int R) {
    if (R < 1 || L > n) return;
    Visit(x);
    int M = (L+R)>>1;
    Tsunami(x<<1, L, M);
    Tsunami(x<<1|1, M+1, R);
}

1.8.　区间加法与区间减法

　　zkw线段树基于区间加法.

　　如果具有区间减法的性质, 那么就如虎添翼.

1.9.　无限的可能性...

　　线段树的每个位置维护的量可能并不是 $O(1)$ 的, 而是 $O(区间大小)$ 的.

　　只要空间允许, 线段树可以拓展到二维的.

2.　永久化的标记就是值

2.1.　永久化的标记就是值

　　现在出现了一个 confusing 的问题: 标记的流行处理手段是下传, 而下传避免不了递归.

　　为了非递归的处理, 我们的核心思想是标记永久化: 访问叶子节点, 每跳到一个父亲, 就根据父亲的标记更新答案.

　　值将转化为标记, 不复存在.

2.2.　区间修改, 单点求值

2.2.1.　通过共同增量转化

　　记 $d_i$ 为 $[i, n]$ 的共同增量.

　　$d_i$ 的维护: 对于区间 $[l, r]$ 增加 $x$ , $d_l$ 增大了 $x$ , $d_{r+1}$ 减少了 $x$ .

　　点 $x$ 的值为 ${init}_x + \sum_{k\ge i}d_k$ .

　　转化成了单点修改, 区间求和问题.

2.2.2.　标记永久化

　　每个节点维护对应区间的共同增量.

　　最初对 $x+M$ 打上 ${init}_x$ 的标记.

　　区间修改就对区间对应节点的标记进行增值.

　　单点求值, 就求这个点到根的标记之和.

2.3.　区间修改, 区间求值

2.3.1.　维护共同增量

　　记 $d_i$ 为 $[i, n]$ 的共同增量.

　　求值的时候差分转化.

　　$\sum_{k = 1}^r val_k = \sum_{k = 1}^r \sum_{i = 1}^k d_i = \sum_{i = 1}^r d_i\times (r - i + 1) = (r+1)\sum_{i = 1}^r d_i - \sum_{i = 1}^r i\times d_i$ .

2.3.2.　标记永久化

　　需要知道每个节点对应的区间, 以方便计算区间的交集大小.

　　可以通过预处理求得.

2.4.　[BZOJ4184] Shallot

　　每个点对应一个集合.

　　若干个操作, 每次将集合 $[l, r]$ 的插入一个数 $x$ .

　　求每个点对应的集合中, 两个数异或的最大值.

　　对线段树上的每一个点开一个 vector , 存每个区间内共同的数.

　　最后将整棵线段树遍历一次, 并在遍历的时候动态地维护线性基.

2.5.　带区间修改的 RMQ

　　记每个节点 $x$ 对应区间内的最大值为 $T[x]$ .

　　每个节点维护标记 $M[x] = T[x] - T[x>>1]$ .

　　查询点 $x$ 的值是, 就直接查询 $\sum_{i\in ancester(x)}M_i$ .

　　查询区间 $[L, R]$ 的时候, 就分开 $L$ 往上和 $R$ 往上来维护两个答案, 每次取max, 然后加上标记, 继续往上跳.

3.　线段树 = ?

　　发现线段树与其余一些数据结构的内在联系, 加深理解.

3.1.　线段树 = 树状数组

　　如果要实现树状数组的功能.

　　那么 zkw线段树 上访问到的节点集合 = 树状数组上的节点.

3.2.　线段树 = 分段哈希

　　给定长度为 $N$ 的序列, $M$ 次操作.

　　操作1: 将区间 $[l, r]$ 的值改为 $w$ .

　　操作2: 将点 $x$ 的值改为 $w$ .

　　操作3: 查询区间 $[l, r]$ 存在多少个值为 $w$ 的点.

　　强制在线.

　　zkw线段树(以坐标为基底) 套 Hash表(以权值为基底).

3.3.　线段树 = 平衡树

　　用 权值线段树 , 实现 平衡树 的功能.

3.4.　线段树 = Trie树

　　Trie树 = 26叉线段树.

zkw线段树