3.3.1 线段树
线段树是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点（并非完全二叉树！！！）。实际应用时一般还要开4N的数组以免越界。
线段树的构造代码如下：
1 |
|
线段树的主要操作包括区间查询（查询给定区间的最小值）和给定节点的更新。
区间查询 int query(int node, int begin, int end, int left, int right);
时间复杂度$O(\log n)$。
（其中node为当前查询节点，begin,end为当前节点存储的区间，left,right为此次query所要查询的区间，实际上我们只想要查询[left, right)的最小值其他的参数是为了计算方便传入的）
线段树区间查询的主要思想是把所要查询的区间[a,b]划分为线段树上的节点，然后将这些节点代表的区间合并起来得到所需信息：（对于节点存储对应区间最小值的线段树来说）
- 如果所查询区间和当前节点对应的区间完全没有交集，那么就返回一个不影响答案的值
- 如果所查询的区间包含了当前节点对应的区间，那么就返回当前节点的值
- 以上两种情况都不满足的话，就对两个儿子递归处理，返回两个结果中的较小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27int query(int node, int begin, int end, int left, int right)
{
int p1, p2;
/* 查询区间和要求的区间没有交集 */
if (left > end || right < begin)
return -1;
/* if the current interval is included in */
/* the query interval return segTree[node] */
if (begin >= left && end <= right)
return segTree[node];
/* compute the minimum position in the */
/* left and right part of the interval */
p1 = query(2 * node, begin, (begin + end) / 2, left, right);
p2 = query(2 * node + 1, (begin + end) / 2 + 1, end, left, right);
/* return the expect value */
if (p1 == -1)
return p2;
if (p2 == -1)
return p1;
if (p1 <= p2)
return p1;
return p2;
}
单节点更新1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Updata(int node, int begin, int end, int ind, int add)/*单节点更新*/
{
if( begin == end )
{
segTree[node] += add;
return ;
}
int m = ( left + right ) >> 1;
if(ind <= m)
Updata(node * 2,left, m, ind, add);
else
Updata(node * 2 + 1, m + 1, right, ind, add);
/*回溯更新父节点*/
segTree[node] = min(segTree[node * 2], segTree[node * 2 + 1]);
}
有n根长度不尽相同的棍子，初始时它们首尾垂直相连，标号为1—n，第一根棍子的下端坐标为(0,0),上端坐标为(0,len[1]),其余棍子依次类推。接下来执行C此旋转，每次输入一个编号num和角度rad，使得第num根棍子和第num+1跟棍子间的逆时针角度变为rad度，求每次旋转后第n根棍子端点的坐标。
解题思路源于[https://www.cnblogs.com/staginner/archive/2012/04/07/2436436.html]
如果我们将其中某一个线段旋转β角，那么这个线段上方的所有线段都会旋转β角，这就很类似线段树中的对区间加上一个常数的问题了，于是不妨向着线段树的思路去想。
接下来一个问题就是β角是相对于谁的，换句话说我们所谓的每个线段都会旋转β角，那么是绕谁旋转的？实际上，如果我们局限于把线段的旋转就会看成是绕某个定点的，这个点就是我们旋转的线段和它下面那个不动的线段的交点，再这样想下去我们就没法处理了，因为每个旋转操作所绕的定点不是唯一的，我们没办法把所有的旋转操作都统一到一起，那么我们就没办法把旋转操作叠加，这样就没法使用线段树了。
但如果换个思路的话，实际上β角还等于这个线段旋转后所在的直线和未旋转前所在的直线的夹角，而直线的夹角是可以用向量的夹角表示的，如果我们把线段看成一个向量的话那么β角就是这个向量旋转的角度。如果这么看的话，所有的旋转操作就可以统一到一起了，也可以叠加了，因为这样不会局限于绕哪个定点，只需要把向量自身旋转一下就OK。
那么我们维护下面两个值：
- 把对应线段集合转到垂直方向（也就是整体旋转，让第一条线段垂直之后，注意并不是单独旋转第一条线段），从第一条线段的起点指向最后一条线段的终点的向量。
- （如果该节点有儿子节点）两个儿子节点对应的部分连接之后，右儿子需要转动的角度（因为s和s+1的角度改变，如果s在左儿子中，那么在全局坐标系内，右儿子也会相应的需要旋转改变坐标）
也就是说，如果节点i表示的向量是$vx_i, vy_i$，角度是$ang_i$，两个儿子节点是chl和chr，那么就有：
对向量旋转的解释可参照[https://www.2cto.com/kf/201610/556382.html]
这样每次更新可在$O(\log n)$的时间内完成。
1 |
|
线段树区间更新
A Simple Problem with Integers
给N个数$A_1, A_2, … , A_n$. 你需要处理两种操作，一种操作是在一个区间上每个数都增加一个数，别一种操作是查询一个区间所有数的和
以目前仅有的单节点更新很难高效滴实现对一个区间同时加一个值，所以我们改进线段树，对每个节点我们维护一下两个数据：
- a. 给这个节点对应的区间内的所有元素共同加上的值
- b. 在这个节点对应的区间中除去a（a就是上面那个a）之外所有其他值的和
如果对于父节点同时加上了一个值，那么这个值就不会在儿子节点被重复考虑，而是在递归计算和的时候再把这一部分的值加到结果中。这样无论是同时加一个值还是查询一段的和复杂度都是$O(\log n)$。
1 |
|
3.3.3 分桶法和平方分割
分桶法是把一排物品或者平面分成桶，每个桶分别维护自己内部的信息，以达到高效计算的目的。
其中平方分割是把排成一排的n个元素每个$\sqrt{n}$个分在一个桶内进行维护的方法的统称。这样的分割方法可以使区间的操作的复杂度降至$O(\sqrt{n})$。
水平分割法相比于线段树实现上要简单，单多数情况下线段树会比水平分割快。
给出一个长度为n的序列a，给出m次查询，每次查询区间[l,r]中第k大的数是什么