线段树与树状数组选讲

1、线段树与树状数组选讲复旦大学计算机科学与技术系 戴涵俊线段树线段树的基本知识及其性质线段树的常用操作及其实现线段树的应用与扩展其它一些例题树状数组树状数组一般模型及其基本思想树状数组实现方法树状数组的常用技巧树状数组的高维扩展一些例题线段树基本知识及其性质基本定义区间a,b)线段树节点T(a,b)内部节点初等区间基本性质节点数深度线段分解数量级问题1：一列n个初始为0的数。执行m次操作，每次操作如下：将该数列中的某个数加上某个数值；询问给定区间中所有数的和。问题1中n为9时的线段树线段树基本知识及其性质线段树的常用操作及其实现存储方式链表存储维护左右端点和左右孩子数组模拟链表堆结构存储类似于满

2、二叉树的形式更紧凑的存储方式线段树的构造void build(Node *cur, int l, int r)cur-Left = l; /区间左端点cur-Right = r; /区间右端点cur-sum = 0;if (l + 1 LeftChild = new Node;cur-RightChild = new Node;build(cur-LeftChild, l, (l + r) / 2);build(cur-RightChild, (l + r) / 2, r);else cur-LeftChild = cur-RightChild = NULL;线段树的查询int query(N

3、ode *cur, int l, int r)if (l Left & cur-Right sum;else int ans = 0;if (l Left + cur-Right) / 2) /如果查询到了当前节点左孩子ans += query(cur-LeftChild, l, r);if (r (cur-Left + cur-Right) / 2)ans += query(cur-RightChild, l, r);return ans;线段树的修改void change(Node *cur, int x, int delta)if (cur-Left + 1 = cur-right) /

4、找到了要修改的位置cur-sum += delta;else if (x Left + cur-Right) / 2)change(cur-LeftChild, x, num);if (x (cur-Left + cur-Right) / 2)change(cur-RightChild, x, num);cur-sum = cur-LeftChild-sum + cur-RightChild-sum;/递归结束后需要用子树的信息来更新当前节点线段树的延迟修改问题2：一列n个初始为0的数。执行m次操作，每次操作如下：将该数列某个区间中所有数加上某个数值；询问给定区间中所有数的和。直接套用问题1解

5、法？累积修改量？更通用的方式：使用lazy-tag将效果作用到叶节点上线段树的延迟修改void change(Node *cur, int l, int r, int delta)if (l Left & cur-Right sum += delta * (cur-Right cur-Left); /更新sumcur-delta += delta; /累积修改else if (cur-delta != 0) /如果有待下传的累积update(cur);if (l Left + cur-Right) / 2)change(cur-LeftChild, l, r, delta);if (r (cu

6、r-Left + cur-Right) / 2)change(cur-RightChild, l, r, delta);cur-sum = cur-LeftChild-sum + cur-RightChild-sum;线段树的延迟修改其中延迟信息下传的方法update可以这么写：void update(Node *cur)cur-LeftChild-sum += cur-delta * (cur-LeftChild-Right cur-LeftChild-Left);cur-RightChild-sum += cur-delta * (cur-RightChild-Right cur-Righ

7、tChild-Left);cur-LeftChild-delta += cur-delta;cur-RightChild-delta += cur-delta;cur-delta = 0;线段树的延迟修改对应查询int query(Node *cur, int l, int r)if (l Left & cur-Right sum;else if (cur-delta != 0)update(cur);int ans = 0;if (l Left + cur-Right) / 2)ans += query(cur-LeftChild, l, r);if (r (cur-Left + cur-R

8、ight) / 2)ans += query(cur-RightChild, l, r);return ans;通过lazy-tag对问题1进一步扩展问题3：一列n个初始为0的数。执行m次操作，每次操作如下：将该数列某个区间中所有数加上某个数值；将该数列中某个区间中所有数都改成某个数值；询问给定区间中那些数的最大值/最小值；询问给定区间中所有数的和。思考以下问题的维护方法：线段树经典问题选讲问题4：逆序对统计给定一个长度为n的数列，求这样的三个元素ai，aj，ak的个数，满足ai ak，且i j k。解法：顺序/倒序插入线段树（可以先进行离散化）、查询线段树进行统计。问题5：矩形覆盖给定N个矩

9、形的位置，求N个矩形并的面积。输入样例210 10 20 20 15 15 25 30 输出样例225朴素方法：将坐标离散化之后模拟，时间复杂度O(n3)坐标离散化（x方向）扫描线方法，做区间覆盖问题用线段树优化动态规划问题6：有n个（n不超过50000）各种长度的栅栏，其中第i个栅栏的y坐标为i。终点在坐标原点（0,0），起点在(s,n)。如下图所示，*为终点，s为起点。 +-S-+-+-+ (fence #N) +-+-+-+ (fence #N-1) . . +-+-+-+ (fence #2) +-+-+-+ (fence #1)=|=|=|=*=|=|=| (barn)-3-2-1

10、0 1 2 3 只能绕过栅栏而不是跳过去。求起点到终点的最短距离。状态转移方程：在转移过程中还需要判断是否栅栏j能够直接到达栅栏i比如：我们反过来考虑状态Fj,0（或者Fj,1）计算出来了后，能够更新之后的哪些栅栏。展开绝对值，并以正确方式查询将线段树扩展到高维（略）四分树，八叉树？树套树！T1(3,5)T1(3,5)下的T2(5,7)线段树与平衡树结合问题7：对于一个长度为n的数列a，你需要高效地维护如下两种操作：修改，将某个数ai改为指定的值t；查询，询问区间i, j中第k小的数字是多少。有修改？线段树套平衡树！如果没有修改？线段树套有序数组一些例题问题9：一群孩子来到一家玩具店，他们每个

11、都想买一些气球，而且他们不希望自己手中的气球有重复的颜色。请帮助店员判断所有的孩子是否能找到符合的气球。第一行为两个整数n和m（1=n=200000,2=m=200000），分别表示气球的颜色数和孩子的数量。第二行为n个整数ai（1=ai=106）表示每种颜色气球的个数。第三行为m个整数bi（1=bi 0) doans ans + sumindexx x - C(x)End whilereturn ans查询操作的时间复杂度就是O（log2N）树状数组更新方法我们关心的是哪些子集包含了这个被修改的元素。修改子集和Function Change(index, delta)while (index

12、 = sumTestIx) thenIndex TestIxvalue value - sumTestIxMask = Mask / 2End whilereturn Index树状数组扩展到高维定义一个二维数组a1.N，1.N，并维护以下两种操作：修改：给ai，j加上一个增量delta；查询：询问左上角a1.x，1.y的和，即 。我们同样用一个二维数组sum维护被分割的“子集”之和，模仿一维情形下的定义，给二维的sum数组定义如下：sumx，y = 二维树状数组查询代码Function Query(indexX, indexY)ans 0while (indexX 0) dotIndexY

13、indexYwhile (tIndexY 0) doans ans + sumindexXtIndexYtIndexY tIndexY - C(tIndexY)End whileindexX indexX - C(indexX)End whileReturn ans单次查询的时间复杂度为O（log2N）2）二维树状数组修改代码Function Change(indexX, indexY, delta)while (indexX = N) dotIndexY indexYwhile (tIndexY = N) dosumindexXtIndexY sumindexXtIndexY + delta

14、tIndexY tIndexY + C(tIndexY)End whileindexX indexX + C(indexX)End while单次修改的时间复杂度为O（log2N）2）树状数组的例题例1：给定一个n*n的矩阵A，其中每个元素不是0就是1。Ai,j表示在第i行第j列的数，初始时，Ai,j = 0（1i，jn）。我们可以按照如下方式改变矩阵：给定一个左上角在(x1,y1)，右下角在(x2,y2)的矩形，通过使用“not”操作改变这个矩形内的所有元素值（元素0变成1，元素1变成0）。为了维护矩阵的信息，你需要写个程序来接收并且执行以下两个操作：1、C x1 y1 x2 y2（1x1x

15、2n，1y1y2n）,代表改变左上角为(x1,y1),右下角为(x2,y2)的矩形区域的值；2、Q x y（1x，yn），代表询问Ax,y的值。先考虑一维情形？转化为我们熟悉的树状数组问题模型例2：在一个二维平面中有n颗星星，任意两颗星星的坐标不同。现在Stan和Ollie决定玩如下一个游戏：Stan首先画一条垂直于x轴的直线，这条直线必须至少经过一个星星，当然也可能会经过几个星星（它们都有同样的x坐标）。接下来，Ollie画一条垂直于y轴的直线，这条直线必须经过一个被Stan所画直线经过的星星。这样，平面就会被划分为如图所示的四个部分。其中，右上和左下的星星个数是Stan的得分，而左上和右下部分的星星个数是Ollie的得分。注意被两条线经过的点都不计算在内。两个人都尽可能想要获得高分。Stan想要最大化自己可能的最小得分。这种方案可能不止一个，对于每种方案，Ollie当然也想得到最大的得分。所以你同时也得求出Ollie可能的得分。枚举中心点。通过树状数组的一些技巧可以求得上面所有的值例3：在