2013年7月25日
* 我们可以直接找到一个数对应的叶子 * 不用自顶向下慢慢地找啊找 * “直接加 4 ”多简单！ * …… * 直接找到叶子？ * 无限遐想中……
*
清华大学 张昆玮
25
2013年7月25日
*
可以直接找到叶子？
清华大学 张昆玮
26
2013年7月25日
(0,5)?
1
2 4 8 9 10 5 11 12 6 13 14 3 7 15
清华大学 张昆玮
41
2013年7月25日
树状 数组
线段 树
*
清华大学 张昆玮
42
2013年7月25日
* 我之前用这种写法做过不少题…… * 大家都说我的代码看不懂 * 我说这就是一个树状数组 * 写树状数组的人说没有lowbit * 我说那就算是线段树吧 * 大家不相信非递归的线段树这么短…… * 我：……
清华大学 张昆玮
13
2013年7月25日
* 原因是区间和的性质非常好 * 满足区间减法 * 区间减法什么的最讨厌了！后面再说！ * 不过直接前缀和不是万能的！ * 如果修改元素的话……
*
清华大学 张昆玮
14
2013年7月25日
数据结构 直接存储原数组 直接存储前缀和 线段树
修改元素 O(1) O(n) O(logn)
树
*
7
2013年7月25日
清华大学 张昆玮
*
如果我给MM的第一印象不到80分的话……
是不是老老实实地早点罢手比较好？
清华大学 张昆玮
8
2013年7月25日
[0,4) [0,2) 0 1 2 [2,4)
[1,4) ?
3
*
清华大学 张昆玮
9
2013年7月25日
* [1,4) in [0,4)
* 左边，[1,2) in [0,2)
*
清华大学 张昆玮
35
2013年7月25日
* 因为树状数组依赖于区间减法 * 区间减法什么的，最讨厌了……后面再讲，再讲 * 反正如果只问问前缀和，不问区间和的话 * 那我也可以只用一倍空间！
*
清华大学 张昆玮36Fra bibliotek2013年7月25日
(…,5)?
1
2 4 8 9 10 5 11 12 6 13 14 3 7 15
* Func Change(n,NewValue)
* n += M; * Tree[n] = NewValue; * While n > 1 do
* n = n >> 1; * Tree[n] = Tree[2n] + Tree[2n+1];
*
清华大学 张昆玮
33
2013年7月25日
* for(T[n+=M]=V, n>>=1;n;n>>=1)
*
清华大学 张昆玮
* 根据 D. E. Knuth 的分类方法
计算机算法可以分为两类：
* 数值算法与非数值算法 * 其中的非数值算法包括：
* 索引 * 分类 * 统计 * ……
*
清华大学 张昆玮
2
2013年7月25日
* POJ上的某题，时限很紧…… * 大家都用树状数组，但是有人只会用线段树呢？ * 而且我可以轻易改出一道不能用树状数组的题 * 在线段树一次次TLE后，有一个ID发帖抱怨 * “下次写一个汇编版非递归线段树，再超时？” * 可是大家都知道，超时的代码已经2k了。 * 其实我写的就是线段树。很快，而且不到1k。
*
清华大学 张昆玮
37
2013年7月25日
(…,5)?
1
2 4 8 9 10 5 11 12 6 13 14 3 7 15
*
清华大学 张昆玮
38
2013年7月25日
(…,5)?
1
2 4 8 9 10 5 11 12 6 13 14 3 7 15
*
清华大学 张昆玮
39
2013年7月25日
1-No
*
清华大学 张昆玮
20
2013年7月25日
1 2 4 5 6 3 7
*
清华大学 张昆玮
21
2013年7月25日
* N 的左儿子是 2N * N 的右儿子是 2N + 1 * N 的父亲是 N >> 1 * …… * 不就是个堆存储么？不用讲了吧？
*
清华大学 张昆玮
22
2013年7月25日
1 10 100 101 110 11 111
* 遗憾的是，这种朴素的方法并不是那么容易实现 * 而且存在严重的效率问题（常数太大）
*
清华大学 张昆玮
17
2013年7月25日
*
清华大学 张昆玮
18
2013年7月25日
*
工欲善其事，必先利其器。
清华大学 张昆玮
19
2013年7月25日
* 虽然可以设计出三叉，四叉，……线段树 * 但是我们先从二叉树开始 * 登高必自迩，行远必自卑 * 多叉怎么办后面再讲（这还要讲？自己研究去） * 为了不处理各种特殊情况，假设二叉树是满的！ * 不是满的？你的总区间是[0,1000)？ * 你就当作[0,1024)不就好了？
A
B
C
*
清华大学 张昆玮
11
2013年7月25日
*
功利点说，没啥用的东西咱不学……
清华大学 张昆玮
12
2013年7月25日
*
区区区间和，用的着线段树？
* 直接把原数组处理成前缀和 * For i=2 to n do
* A[i] += A[i-1]
* Ans(a,b) = A[a] - A[b-1]
*
清华大学 张昆玮
3
2013年7月25日
* 运行速度快 * 适应能力强 * 编写方便 * 结构简单 * 容易调试 * 关键在于灵活实现
*
清华大学 张昆玮
4
2013年7月25日
*
为什么在《算法导论》和黑书中都难见到其踪迹？
清华大学 张昆玮
5
2013年7月25日
* 计算几何在长期的发展中，
诞生了许多实用的数据结构。
*
清华大学 张昆玮
23
2013年7月25日
* 字母树！ * 存放的是100,101,110,111四个串！ * 每个节点存的是以这个节点为前缀的所有节点和 * 例：1中存的是所有四个以1开头的和。 * 似乎从 100 到 111 就正好是原数组 * 貌似……下标减 4 就行了？
*
清华大学 张昆玮
24
2-1 3-No
4-2
5-No
6-3
7-No
*
清华大学 张昆玮
40
2013年7月25日
* 这不就和树状数组一样了？ * 本来就应该一样。 * 回过头说，树状数组究竟是什么？ * 就是省掉一半空间后的线段树加上中序遍历 * 计算位置需要lowbit什么的 * 我们用的是先序遍历，符合人的思考习惯。
*
* T[n]=T[n+n]+T[n+n+1];
* 没了？ * 没了。
*
清华大学 张昆玮
34
2013年7月25日
* 仅使用了两倍原数组的空间 * 其中还完整地包括了原数组 * 构造容易:
* For i=M-1 downto 1 do T[i]=T[2i]+T[2i+1];
* 太好写了！好理解！ * 自底向上，只访问一次，而且不一定访问到顶层 * 实践中非常快，与树状数组接近 * 为什么呢？后面再讲。
存放在树的根部，所以下传标记做什么？
*
清华大学 张昆玮
48
2013年7月25日
*
庄周梦蝶而已
清华大学 张昆玮
49
2013年7月25日
* 一根线段，支持区间染色。
询问区间是否同色？
* 区间染色需要使用染色标记 * 询问的时候就直接看标记嘛
1表示红色，2表示蓝色，3绿色，0杂色
*
清华大学 张昆玮
50
2013年7月25日
* 2为红色，3为蓝色，1为杂色
修改3为红色 查询1，杂色？
* 永久化的标记就是值啊！值是自动维护的啊！ * 其实我们的修改算法在修改3的时候已经维护了1 * 自底向上顺便重算所有遇到的节点标记即可 * If (Mark[x]==0 and Mark[2x]==Mark[2x+1])
* If ((s and 1) == 0) Answer += Tree[s + 1]; * If ((t and 1) == 1) Answer += Tree[t – 1]; * s = s >> 1, t = t >> 1;
*
清华大学 张昆玮
29
2013年7月25日
* for (s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1) {
*
清华大学 张昆玮
43
2013年7月25日
*
懒惰即美德。
清华大学 张昆玮
44
2013年7月25日
*
噩梦的开始
清华大学 张昆玮
45
2013年7月25日
* RMQ (Range Minimum Query) * 区间最小值查询 * 线段树 * 支持区间修改：
* 某一区间的数值全部增加一个可正可负的数
*
清华大学 张昆玮
27
2013年7月25日
(0,5)?