树状数组总结

2016-12-14 09:52:12来源:http://blog.csdn.net/fjsd155/article/details/6883792作者:fjsd155人点击

Poj上的一些题:


1)poj1195Mobile phones 难度:1


题意:给定n*n矩阵,和几种在线操作,包括对某一点(x,y)值修改,查询一个矩形(x1,y1,x2,y2)的元素和。


分析:用二维树状数组维护即可。


2)poj2299Ultra-QuickSort 难度:1


题意:给你n个不同的数,求逆序对个数。


分析:有两种方法:归并排序;树状数组。


这里提一下树状数组的方法。倒着处理,每次统计比当前元素值小的已经处理完的元素的个数,所有的累加起来就是答案。


3) poj2352star 难度:2


题意:按y递增的顺序给出n颗星星的坐标(y相等则x递增),每个星星的等级,等于在它左边且在它下边(包括水平和垂直方向)的星星的数量,求出等级为0到n-1的星星分别有多少个。


分析:由于星星的坐标是按y的递增给出的,那么就只需考虑水平方向就好了,如果给出一个星星的坐标为(a,b),那么它的等级就等于前面已经输入的x坐标在[0,a]区间的星星数量。


4)poj3067Japan 难度:2


题意:顺序给两组平行的点依次编号1~N和1~M,给定K个线段在两组点之间,求相交(cross)的线段对有多少个,同一个起点或终点不算相交。


分析:设1~n这组点属于A组,1~m属于B组。用树状数组记录当前每个B中的点与多少个已处理完的A中的点相连,按n~1的顺序处理,即倒着做。例如当前处理的A中的为x,与x相关的B中的点有:a,b,c;则将当前B中1~a-1所有点的值的和(每个点的值即为该点与多少个已处理完的A中的点相连)加入答案,为什么呢?当前B中1~a-1所有点的值都是A中大于x的点贡献的;同理,将1~b-1所有点的值的和加入答案,将1~c-1所有点的值的和加入答案。


5)poj2155matrix 难度:3


题意:一个n*n的01矩阵,和几种动态操作,包括对子矩阵(x1,y1,x2,y2)的所有元素异或,查询某一点(x,y)的元素值。


分析:仅需修改矩阵四个顶点的值,这四个点是:


(x1,y1)、(x1,y2)、(x2,y1)、(x2,y2)。


对于询问(x,y),用树状数组统计(x,y)右下方的元素和mod 2即为答案。


但对于修改的矩阵出现x1=x2或y1=y2时会出现西西,我是这么避免出错的:


将矩阵每个元素拆成四个点(行数*2,列数*2),修改矩阵(x1,y1,x2,y2)则对这四个修改:


(x1*2-1,y1*2-1)、(x1*2-1,y2*2)、 (x2*2-1,y1*2-1)、(x2*2-1,y2*2)。


6)poj3321apple tree 难度:2


题意:一棵具有n个节点的树,一开始,每个节点上都有一个苹果。现在给出m组动态的操作:(C,i)是摘掉第i个节点上面的苹果(若苹果不存在,则为加上一个苹果),(Q,i)是查询以第i个节点为根的子树有几个苹果(包括第i个节点)。


分析:树状数组。这道题重点怎么建立树到树状数组的映射关系:利用dfs遍历树,对每个节点进行两次编号,第一次搜到第i个节点时的时间戳,为这个节点管辖区间的下限L[i],然后搜这个节点的子节点,最后搜回来后的时间戳,为这个节点管辖区间的上限R[i] (也为这个节点的下标),如下图所示。接下来就是树状数组部分了。



7)POJ 2481 Cows 难度:3


题意:每个奶牛都有一个吃草的范围,对应一段线段 [s, e], 如果某一头a的区间覆盖了另一头b 的区间,就说a 比b 强,求比每头奶牛强的奶牛数。


分析:此题类似于线段覆盖cover那题,此处不讲解,可以参考cover那题的解题报告。


(这题交了n遍,原来poj卡Qsort!!要用随机Qsort)


8)POJ 2029 Get ManyPersimmon Trees 难度:1


题意:给定N*M的矩形和T个点,让你求A*B的子矩形最多能覆盖几个点。


分析:枚举矩阵的右上端点,用树状数组统计该矩阵内点的个数。


9)POJ 1990 MooFest 难度:3


题意:有n头牛,不同的听力值v,当i,j想要通话时,需要max(v(i),v(j))*|dist[i]-dist[j]|的volume,问这n*(n-1)/2对牛总共的volume是多少。


分析:处理两个东西:max和abs。对于max可以Qsort解决:v大的先处理,处理完就删掉。对于abs,可以拆成两部分处理,设当前的牛为i,对于未处理的牛j,


若dist[j]

abs(dist[i]-dist[j])=dist[i]-dist[j],


否则(设这种牛有t2个)


abs(dist[i]-dist[j])=dist[j]-dist[i]。


故所有j与i的volume值总和为:t1*dist[i]-sigma(dist[j])+sigma(dist[j])-t2*dist[i].


t1与t2可以用树状数组统计,sigma(dist[j])与sigma(dist[j])也可用树状数组统计。


平时考试的一些题:


10)修路(10月15日ldl大牛出的一道题)难度:3


题意:有n个城市和n-1条道路,呈树状分布,其中省会为1号(根)节点。这n-1条路原先是羊肠小道,后来逐渐变为水泥大道,这期间省长小L有多次出访其他n-1个城市。给你m个操作,操作分为两种类型:修建城市x和y之间的道路、询问小L访问城市x时经过了多少条羊肠小道。(初始时所有道路都为羊肠小道)


分析:类似于上一题apple tree,也是利用了映射转化的思想。先对这棵树dfs,求的开始经过每个节点i的时间戳L[i]和最终离开每个节点i的时间戳R[i],将L[i]和r[i]加入到树状数组中,并将l[i]对应的值赋为1,表示i与i的父亲间有一条小道;将r[i]对应的值赋为-1。因此,对于以i为根的子树中的节点统计羊肠小道时能够统计到节点i与i的父亲间的小道,儿对于不是以i为根的节点统计不到i与i的父亲间的小道(因为离开i时又减去了1)。修i与其父亲间的小路时,只需将L[i]的值减1,R[i]的值加1即可(因为要使不是以i为根的节点不受影响)。注意每次统计的答案要减去1,因为树的根节点没有父亲,也就不存在根节点与其父亲间的小路!


11)线段覆盖cover(某日数据结构小考的题目)难度:3


题意:给你n条线段(左端点为l[i],右端点为r[i]),哪条线段覆盖了最多的线段,输出这个最大值。


分析:按左端点递减的顺序处理,先统计右端点小于当前处理线段的右端点的已处理线段数量,统计的结果即为当前线段覆盖的线段的数量,然后将当前线段的右端点加入树状数组中。由于端点值较大,需要离散化。


12)9月24日xqz的模拟题中有一道叫tree的题,


实际上来自Hdu 3015Disharmony Trees(xqz copy的!)


此题同poj1990.


hoj上的一些题(现已找不到hoj这些题了):


13)Hoj1867 经理的烦恼 难度:0


一维树状数组+判素数,此处不详细讲。


14)Hoj2430 Counting the algorithms难度:2


题意:给出2*N的序列,每个数∈[1,N]出现2次2个数之间的间隔为得分,求得一个得分后会删除这两个数,问最大得分。


分析:贪心+树状数组。从后往前删除数,用树状数组求得sum(x)个数,对于嵌套的、相互独立的,先删除谁都没关系但对于包含关系的,必须先删除外围的,所以从后开始(从前开始也一样)。


15)hoj2275 Number sequence难度:2


题意:计算序列 a[] 中, 当 i < j < k, a[i] < a[j] >a[k], 这样的子序列个数。


分析:对于每个元素j,用树状数组统计i的个数s1[i],使i满足以下条件:Ij,a[k]

其他网站:


16)Sgu 180 Inversions:求逆序对(同poj2299)


17)SPOJ 1029 Matrix Summation:基本二维树状数组,


同poj1195


18)tju3243 Blocked Road 难度:2


题意:1-N个村庄,1-N条路,注意1到N有一条回路,然后不断进行操作,修复或破坏他们之间的路,然后查询是否有路从A到B


分析:用树状数组记录每条路是否完好,完好则记为1,否则记为0,判断x与y是否连通,只需判断sum(y-1)-sum(x-1)是否等于y-x;还可以反向走,判断sum(n)-sum(y-1)+sum(x-1)是否等于n-y+x即可。


19)SPOJ227 Ordering the Soldiers 难度:4(好题)


题意:有n个点,标号1到n,给定数组b[i]表示i前面比a[i]小的点的个数,求a[]数组。


分析: 我们可以先想想朴素的做法,比如b[] = {0, 1, 2, 0, 1},我们用数组c[i]表示还存在的小于等于i的个数,一开始c[] = {1, 2, 3, 4, 5},下标从1开始。


我们从右向左扫描b[]数组,b[5] = 1,说明该点的数是剩下的数中第2大的,也就是小于等于它的有2个,即我们要找最小的j符合c[j] = 2(这里可以想想为什么是最小的,不是最大的,挺好理解的),而c[]是有序的,所以可以用二分来找j,复杂度为O(logn),但现在问题是每次更新c[]要O(n)的复杂度,这里我们就想到树状数组,c[i]表示还存在的小于等于i的个数,这不正好是树状数组的看家本领吗~~


所以处理每个位置的复杂度为O(logn * logn),总的复杂度为O(n * logn * logn)。


20)hdu 2852KiKi's K-Number 难度:3


有三种操作:插入元素x,删除元素x,询问比x大的数中第k大的。


这题与上面那题类似,只是要求比a大的第k大的数,那我们用Getsum(a)求出小于等于a的个数,那么就是要我们求第k + Getsum(a)大的数,而删除操作只要判断Getsum(a) – Getsum(a - 1)是否为0,为0则说明a不存在。


参考资料:


某俩牛人空间:


http://hi.baidu.com/lilu03555/blog/item/4118f04429739580b3b7dc74.html


http://hi.baidu.com/evilsham/blog/item/8540236da505c73eab184c92.html


及“依然”等大牛博客。

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台