树状数组专题【完结】

1 国外的论文点击打开链接

2 我的总结点击打开链接

任何能够造成树状数组下表为0的操作都会使得程序TLE，这是个很重要的地方！

第一题 poj 2299 Ultra-QuickSort

点击打开poj 2299

思路: 离散化+树状数组
分析:
1 题目的意思就是要求逆序数对
2 题目的输入个数有500000的规模但是每个数的最大值为999999999，因此我们需要离散化这些数据
3 对于数据9 1 0 5 4我们离散化成5 2 1 4 3
那么对于输入一个树a[i]我们去求一下它的离散化后的id，然后去求前面比这个id大的个数
4 由于getSum(x)函数的求和是求[1,x]而不是[x，MAXN),所以我们可以换成求小于等于id的个数即getSum(id),然后i-1-getSum(id)就是比id大的个数，最后在更新一下treeNum[id]

点击查看代码

第二题 poj 2352 Stars

点击打开poj2352

分析：
1 题目是要求出每一个点的左下(正左+正下)有几个星星，那个这个点就是第几层，最后输出0～n-1层的点的个数。比如样列编号为5的星星，左下有3个星星那么5就处于第三层
2 利用树状数组，我们知道树状数组C中，C[i]表示的是原先数组A中的某一段和。题目明确指出输入的时候是按照y值增大的顺序（y相同是x增大），那么我们应该要用什么做为原先的数组A呢，很显然就是X轴，就是A[2]表示x = 2的点的个数。那么当新加入一个点的x值为2的时候，A[2]++，这个时候就是要更新C[2]，C[2+lowbit(2)]...

3 那怎么求某个点的左下有几个星星呢，很显然处在左下的点的x值肯定小于等于当前点的，那么就是相当与树状数组求和，那么整道题的思路就完成
4 注意更新树状数组的时候，注意x<=MAXN，不是输入的n。因为更改了A[x]，就要更新C[x] , C[x+lowbit(x)]...

5 题目输入的x的坐标可能为0，所以这边我们把所有的x+1，这就避免了TLE

点击查看代码

第三题 poj 1195 Mobile phones

点击打开poj 1195

思路: 二维树状数组
分析:
1 给定一个矩阵和三种操作 1 a b x表示把[a,b]值加上x，2 L B R T表示L <= x <= R , B <= y <= T
求这个小矩形的面积 3表示输入结束
2 简单的二维树状数组，但是这边要注意的是操作2的时候一定不能够把维度给弄反了，L R表示的是x的范围而B T表示
的是y的范围
3 题目还有一个trick就是当[a,b]加上x后如果值为负数，那么应该把值设为0

点击查看代码

第四题 poj 2481 Cows

点击打开poj 2481

思路：树状数组
分析：
1 题目给定n头牛所在的区间，然后问每头牛都有几头牛比它强壮
2 根据题目如果牛i的区间是[Si , Ei]，牛j的区间是[Sj , Ej]那么牛i要比牛j强壮的话，那么就有Si <= Sj && Ei >= Ej && Si-Ei > Sj-Ej;
3 那么根据上面的条件，我们应该要先对n头牛的区间排序”按照S从小到大，相同S按照E从大到小排序“
4 显然排完序之后我们能够满足Si <= Sj && Ei >= Ej，但是我们应该要注意到Si-Ei > Sj-Ej，说明了排完序之后不能够相等
5 我们利用E做树状数组，如果前后两个相当那么直接更新即可
点击查看代码

第五题 poj 3067 Japan

点击打开poj 3067

思路：树状数组
分析：
1 题目要求的是找到所有直线的交点总数，并且题目明确指出两条直线之间最多只有一个交点
2 我们应该先对这些直线进行排序：按照左边的编号从小到大，左边编号相同时按照右边编号从小到大。那么假设现在有一条直线1-3，那么能够和这条直线有交点的肯定是右边的编号大于3的，那么这个过程就可以利树状数组求和得到，求和完毕还要更新树状数组。
3 由于题目的k没有给定，那么最坏的情况1+2+...k，

4 数据会超过int , 所以我们应该选择long long.

点击查看代码

第六题 poj 2029 Get Many Persimmon Trees

点击打开poj 2029

思路: 简单的二维树状数组
分析:
1 题目给定一个人h*w的矩阵，给定n个点表示该点上面有柿子树，求给定一个t*s的矩阵的最多的柿子树的个数
2 简单的二维树状数组，加入一个点的时候更新树状数组
3 题目的范围最大为100，很明显就是要暴力枚举起点，然后求最大值即可

点击查看代码

第七题 HIT 2275 Number sequence

点击打开HIT2275

分析:

1 题目要求的是总共的搭配方式，满足Ai < Aj > Ak.并且i j k不同

2 我们开两个树状数组，第一个在输入的时候就去更新。然后我们在去枚举Aj 同时维护第二个树状数组，对于AI来说就是在第二个树状数组里面求和

然后在通过第一个树状数组就可以求出Ak的个数，把结果相乘即可

点击查看代码

第八题 HIT 1867 经理的烦恼

点击打开HIT 1867

思路: 树状数组
分析:
1 题目要求的是给定一个区间求这个区间质数的个数
2 题目给定n条命令和每个店的初始的值，那么我们初始化的时候就要通过判断给定的初始值是否为质数来初始化
3 因为要求的是质数的个数，那么我们可以这么想，假设现在改变了店铺x的值，那么我们通过判断前后是否是质数的关系来更新树状数组
4 求区间的质数的个数的时候直接求即可

点击查看代码

第九题 SGU 180 Inversions

点击打开SGU 180

思路: 树状数组+离散化

分析:

1 题目给定n个数，每个数最大为10^9 , 最小为0，求多少个匹配使得1<=i<j<=n并且A[i] > A[j]

2 因为数的最大值为10^9.所以我们应该利用离散化的思想。然后在利用树状数组求个数即可

3 注意由于输入的值由可能为0，我们应该在输入的时候就把所有的值加上1

点击查看代码

第十题 SPOJ 1029 Matrix Summation

点击打开SPOJ 1029

思路: 二维树状数组

分析:

1 简单的二维树状数组，注意因为数据量很大TLE了多次，之后把memset改成for循环A了

点击打开查看代码

第十一题 poj 2155 Matrix

点击打开poj 2155

1 题目给定两种操作，第一种是给定左上角和右下角的下标，把这个子矩形里面的0/1进行互换，第二种是问某个点的值

点击打开查看代码解析

第十二题 poj 3321 Apple Tree

思路: 树状数组

分析:

1 题目给定一棵树，然后有n个树枝，每个树枝上面初始化有1个苹果，现在有m个操作

2 题目给定的是一棵树，我们应该考虑怎么把这棵树映射成一个数组，并且跟节点和儿子节点的编号是连续的。这一步我们可以利用dfs来做，利用时间撮的概念，第一次到达的时间作为起始的时间，第二次到达的时间为终点的时间，下图就是一个例子

3 这一题的时间卡vector卡的紧，所以我们应该利用邻接表来存储图

4 当我们求出了每一个节点的时间戳之后，那么我们就可以利用树状数组来求，每一个点的时间戳区间就是这个节点的所有子树包括本身的和，那么这个和可以利用树状数组进行求解，更新的时候由于我们只要更新起始位置即可，这样能够保证是对的

点击打开查看代码

第十三题 poj 1990 MooFest

点击打开poj 1990

思路: 树状数组

分析:

1 题目给定n头牛的听力v[i]. 现在规定两头你i和j如果要进行交流的话那么消耗的能量就是dis(i,j)*max(v[i].v[j])，现在问n头牛总共的n*(n-1)*2种方式消耗的总的能量

2 题目要求的是所有的牛的交流方式的总的消耗能量

看这个样例

3 1

2 5

2 6

4 3

那么所有的区间为[1.3],[1,5],[1,6],[3,5],[3,6],[5,6]

那么总和为4*dis[1.3]+3*dis[1,5]+3*dis[1,6]+4*dis[3,5]+4*dis[3,6]+2*dis[5,6] = 4*(dis[1.3]+dis[3,5]+dis[3,6])+3*(dis[1,5]+dis[1,6])+2*(dis[5,6]);

那么题目要求的ans = ∑(v[i]*(所有比v[i]小的牛的坐标的总和))

3 那么我们来分解这个式子，我们对点按照音量的值从小到大排完序之后

那么对于任一的一点i，i之前的牛的音量值肯定小于v[i]，但是坐标的值可能比x[i]大也可能比x[i]小，因此我们应该分成两部分来考虑，就是坐标是i的左边和右边

首先考虑左边的情况，假设左边比小于等于v[i]的牛有三头坐标分别为a b c，那么左边的值就是v[i]*(x[i]-a)+v[i]*(x[i]-b)+v[i]*(x[i]-c) => v[i]*(3*x[i]-(a+b+c))

那么我们假设左边小于v[i]的牛有countLeft头，总的坐标为totalLeft，那么左边的值为v[i]*(countLeft*x[i]-totalLeft);

接下来考虑右边的情况，由于我们已经按照v的值排序，那么我们能够很好的计算出小于等于v[i]的音量值的总的坐标之后，我们设为totalDis，那么根据左边求出的小于

等于v[i]的个数为countLeft，那么右边的个数为i-countLeft，那么同理右边的坐标之和为totalDis-totalLeft , 那么右边的值为v[i]*(totalDis-totalLeft-(i-countLeft)*x[i]);

那么对于排序后的第i头牛来说比它小的音量的牛的值为v[i]*(countLeft*x[i]-totalLeft)+v[i]*(totalDis-totalLeft-(i-countLeft)*x[i]);

4 我们已经知道了公式，现在我们只要去求countLeft和totalLeft即可，由于我们已经按照v的值排序， 那么我们只要对坐标建立两个树状数组即可。一个用来存储个数，一个用来存储坐标之和，那么对于第i头牛来说我们就能够在O(logn)的时间内求出countLeft和totalLeft

点击打开查看代码

第十四题 hdu 3015Disharmony Trees

点击打开hdu 3015

思路: 树状数组

分析:

1 题目给定n棵树的横坐标和高度，然后给定横坐标排序后的rank_f已及树的高度排序后的rank_s，规定两颗树的FAR为abs(rank_f[i] , rank_f[j]) , SHORT为min(rank_s[i] . rank[_sj])，那么i和j的组合的值为FAR*SHORT，求所有组合方式的总和

2 我们按照树的高度从大到小排序，然后我们分别求出每棵树的rank_f和rank_s ， 然后我们就可以利用poj 1990

的思路去做

点击查看代码

第十五题 SPOJ 227 Ordering the Soldiers

点击打开SPOJ 227

思路: 树状数组

分析:

1 给定一个n个数的序列假设为b数组，那么b[i]表示的是i之前比第i个数大的个数，比如样例的2 1 3对应的b数组是0 1 0，现在要求a数组，已知a数组的值是1～n

2 我们通过b数组可以知道a数组的情况，因为前面的数会影响后面的数，那么我们从后面枚举b数组，这样我们可以知道对于第i个数i-b[i]就是剩下的i个数中的第几大的数，比如第二个样例

0 1 2 0 1 , 那么i为5的时候i-b[i] = 5-1 = 4，说明第5的数是1～n中的第四大的数也就是4，接下来我们删除掉4，i为4的时候i-b[i] = 4-0 = 4也就是第四个数是剩下的第4大的数也就是5，以此类推.....

3 通过2的思路，我们发现很简单，但是我利用vector的时候TLE了，说明我们需要一个更高效率的算法

4 由于n个数是1～n，那么我们初始化一个树状数组treeNum[i] = i;

表示的是前面有i个数比它小，那么我们可以知道树状数组是一个单调递增，为什么呢？因为我们初始化每个点的值都还没被取过，那么区间[1,i]的和为i，所以i越大和越大。

通过第2点的分析我们可以知道，我们能够求出每一个数的排名，也就是前面比它小的个数，那么这个就是树状数组保存的值，所以我们可以通过二分答案来求，我们取了某个数之后就标为true，然后树状数组进行单点更新。

但是我们会遇到一个问题就是比如第二个样例中我们把4和5取完之后我们会发现[1,3]和[1,4]和[1,5]这三个区间的和为3，但是只有3是符合的，因为4和5被取了，所以我们在二分的时候应该注意判断值是否被取过

5 那么我们来分析一下时间复杂度，我们需要枚举b数组为O(n)，每次二分的时间为O(logn)，每次更新树状数组的时间为O(logn)，总的为O(n*logn*logn)

点击打开查看代码

第十六题 hdu 2852 KiKi's K-Number

点击打开hdu 2852

思路: 树状数组

分析:

1 题目给定三种操作: 0 x 表示把x插入容器 ; 1 x 表示删除一个x如果没有x则输出 No Elment! ; 2 a k 表示比a大的数中的第k大的数 如果没有输出No Find!

2 我们先来看一下树状数组的功能，树状数组能够在在logN的时间内求出某段区间的和，那么对于2 a k这种操作我们可以看成是求是否有x满足[a,x]这个区间的和为k，那么这样就变成了树状数组的求和问题了。那我们再来考虑插入和删除操作，插入一个x相当于更新树状数组，删除x注意多个的情况

3 通过第2点的分析我们知道我们主要是否有区间[a , x]的和为k，那么我们知道对于树状数组来说从a开始的区间的和是递增的，因此我们可以通过二分答案，然后去求出满足的x

4 那么我们来分析一下时间复杂度，枚举操作为O(n)，每次操作的最坏时间为O(logN)，因此时间复杂度为O(n*logN);

点击查看代码

第十七题 hdu 1166 敌兵布阵

点击打开链接hdu 1166

思路: 裸题

点击查看代码

第十八题 hdu 1556 Color the ball

点击打开hdu 1556

思路; 树状数组

分析:

1 简单的区间更新，单点查询问题

点击查看代码

第十九题 hdu 1892 See you~

点击打开hdu 1892

思路: 二维树状数组

分析:

1 题目给定4种操作: S x1 y1 x2 y2 询问以(x1 , y1) - (x2 , y2)为对角线的矩形的面积，但是这个对角线不一定是正对角线。A x1 y1 n 把点(x1 , y1)加上n。D x1 y1 n点(x1 , y1)减去n如果不足n就全部删除即可。M x1 y1 x2 y2 n 把点(x1 , y1)点值中扣除n加到(x2 , y2)，如果不过n则把(x1 , y1)值全部加到(x2 , y2)

2 简单的二维树状数组，但是注意在求矩形的面积的时候我们应该把矩形转化成正对角线的模式这样才不会错，在更显点的时候由于我们需要判断值的大小，所以我们需要一个数组保存每个点的值

点击查看代码

第二十题 hdu 2642 Stars

点击打开hdu 2642

思路: 二维树状数组

分析: 裸题

点击查看代码

第二十一题 hdu 3584 Cube

思路: 三维树状数组

分析:

1 点击打开查看论文 建议先看看这篇论文，然后就懂了，裸的三维树状数组

点击查看代码

第二十二题 hdu 2838 Cow Sorting

点击打开hdu 2838

思路: 树状数组

分析:

1 题目和求逆序数那题很像，裸题

点击查看代码

第二十三题 hdu 1394 Minimum Inversion Number

点击打开hdu 1394

思路: 树状数组

分析:

1 题目要求的是n个数的n个序列中找到的最小逆序数对

2 首先我们都知道所谓的逆序数对就是给一个序列，如果前面的数比当前的数大，那么这两个数就是逆序数对。比如4 1 3 2中逆序数有 4 1, 4 3, 4 2, 3 2

3 那么我们可以很快的利用树状数组求出起始数组的逆序数对，那么我们接下来考虑把第一个数换到最后一个位置的情况

假设现在起始的序列的逆序数对有sum，那么第一个数num[1]换到最后一个位置的后果就是使得所有比num[i]小的数度不能和num[i]构成逆序数了，那么直接减少的个数就是n-1-num[i]，但是那么比num[i]大的数可以和num[i]构成逆序数，因此增加了n-num[i]个。因此换完之后的序列的逆序数对为sum-(n-1-num[i])+n-num[i];

4 因此我们只要去做n次的比较，求出的最小值即为ans

点击查看代码

第二十四题 hdu 2688 Rotate

点击打开hdu 2688

思路: 树状数组

分析:

1 题目给定n个数求满足 i < j并且 F[i] < F[j]的个数

2 首先我们可以利用树状数组求出起始序列满足条件的个数sum。那么我们考虑如何把区间[s , e]进行交换，通过题目我们可以知道每一次的交换只是把区间的第一个数换到区间的最后一个位置，那么我们可以考虑假设区间第一个数为x ，区间里比x小的为min，比x大的为max，那么x换到区间的最后一个位置的结果就是原来大于x的数度不能和x构成一对，原来小于x的现在度满足了，那么相当于做一次的变换sum = sum-max+min;

点击查看代码