算法和数据结构第一讲——树状数组 by hez2010
本帖最后由 hez2010 于 2016-10-30 20:55 编辑准备做一个算法和数据结构的合集，时间比较紧，可能更新比较慢（话说论坛支持markdown么。。）。那么就从这里开始吧。
--------------------------------------------------
树状数组Binary Indexed Tree
事先要明白这东西是干啥的。
在一些数列问题中，使用一般的算法时间复杂度太高，空间复杂度又无法让人接受，那么此时树状数组将会是一个很好的选择。
看完后是不是一脸懵逼？
这么给你说，现在给你一个数组a，你需要把a[ i]的值加上一个delta，怎么办？【我猜你一定会说a[ i]+=delta不就好了么】
是没错，然后现在要在这个数组中求出a[ 1]+...+a[ k]，怎么办？【我猜你一定又会说int ans=0; for (int i=1;i<=k;i++) ans+=a[ i];不就好了么】
【真聪明】
那按照你的方法，改一个数值只需要将a[ i]加上一个值，这种仅需要一次就能完成的操作，我们称为O(1)的时间复杂度
然后求和呢？如果我要从a[ i]一直求和到a[ k]，那么我需要将数组a从下标1遍历到k，执行k次操作，时间复杂度为O(k)（通常不这么说，而是说成O(n)）
那么如果我对一个数组有大量的修改、查询操作，那你岂不每一次查询都要遍历一次，查询n次，时间复杂度就成O(n^2)了，这怎么能行？查询规模稍微大一点的话岂不要很久？【此方法淘汰】
所以，为了解决这个问题，我们引入一个东西叫做树状数组。树状数组适用于 修改次数不太大、查询次数非常多的情况。
什么叫树状数组呢？就是像一颗树一样的数组（废话）
基本思想就是，我们将整个数组分解为一系列的子集，进而进行求和，但是要注意，分解出来的子集不能相交。
怎么分解呢？考虑用二进制思想
例如，15=2^3+2^2+2^1+2^0，那么类似的，可以将a1+a2+...+ak也分解为几个子集的和。
那么怎么分呢？一般来说，如果k的二进制表示中有m个1，那么我们就将其分解为m个子集的和，所以，我们可以给出以下的子集划分：
下标二进制子集
111
2101~2
3113
41001~4
51015
61105~6
71117
810001~8
910019
其中，下标代表了每个子集的编号，子集即代表包含的a中的元素。比如说，下标为8，那么这个子集里就包含了a[ 1]+...+a[ 8]。我们把这个包含各个子集的数组记为sum，那么sum[ 8]=a[ 1]+...+a[ 8]。
有什么用呢？你想，如果我想求a[ 1]+...+a[ 8]，我就不用按照以前的方法从a[ 1]遍历一直加到a[ 8]，而是直接返回sum[ 8]就行了，因为按照这个划分之后，sum[ 8]中存储的就是原来a[ 1]+...+a[ 8]的值！
看一个例子：
下标1234567891011!2
a数组201102301021
前缀和2234469910101213
sum数组221402391124
按照这个划分，子集和就很明晰了，求a[ 1]+...+a[ k]的方法也很明晰了：
子集和查询树
http://img.blog.csdn.net/20160629142356437
图中的每一个长方形都代表每个子集对应的部分和，深色代表了自己下标所对应的值a[ i]，浅色代表还需要维护的别的值a[ k]~a[ i−1]
对于每个查询，我们如果顺着黑色的实线依次走下去，就可以得到对应的前缀和了。
http://img.blog.csdn.net/20160629004102424
如此一来，对于每个查询，我们找到树中对应标号的结点，顺着边一直走到0，依次累加对应的子集和，到根的时候，我们就得到了最终的前缀和。通过观察我们还能发现：每个结点的深度代表了对应查询所需要累加子集和的数量，也就是对应数字的二进制中1的个数。另外，除了那个虚拟的根结点0之外，其他的每个结点的孩子个数都等于其二进制中末尾0的个数。因此我们叫它树状数组也叫Binary Indexed Tree
sum的下标12345678
二进制表示110111001011101111000
包含的元素个数C12141218
C的二进制表示110110011011000
通过观察我们发现，元素个数C的二进制表示就是对应下标的二进制表示中最低位的1所在的位置对应的数！求这个C运用了低位技术（Lowbit），基于位运算，我们便能得到强大的lowbit函数。那么如何快速根据下标求得这个C呢？
不难得到求法：
方法1：C(i)=i-i&(i-1)
方法2：C(i)=i&(-i)//利用计算机中补码
现在我们知道了查询a[ 1]+...+a[ k]时遍历的方法，就可以查询前缀和了。
int C(int i){ //lowbit
return i&-i;
}
int query(int i){
int ans=0;
while (i>0) {
ans+=sum[ i];
i-=C(i);
}
return ans;
}
时间复杂度从O(n)降到了O(log n)，这是个不小的优化。
修改方法：
用了树状数组，当我们需要修改a[ i]的时候（给a[ i]加个delta），就需要给所有包含a[ i]的子集都加上这个delta
那么同理，利用C(i)和lowbit进行遍历、修改
void change(int i,int delta){
while (i<=n){
sum[ i]+=delta;
i=i+C(i);
}
}
如果此时你一脸懵逼，听我举个例子：
现在我要给a[ 6]加个delta，以前不用树状数组的时候，直接a[ 6]+=delta就行了，但是现在既然用了树状数组，树状数组里存的都是各个子集的和，所以为了完成这个修改，我们需要给所有包含a[ 6]的子集都加上delta，所以，我们需要给树状数组中的sum[ 6]、sum[ 8]都加一个delta才行。
上面的查询都是查a[ 1]+...+a[ k]，也就是前缀和，那有没有什么方法求a[ i]+a[ i+1]+...+a[ j]呢？（i<j）
很简单，query(j)−query(i−1)
那我不想求和了，我想知道ai是多少，怎么办？
也很简单，query(i)−query(i−1)就是。
进一步，从查询树中，我们可以发现：a[ i]=sum[ i]−(query(i−1)−query(LCA(i,i−1)))，其中LCA为最近公共祖先。
int getval(int i){
int ans=sum[ i];
int lca=i-C(i);
i--;
while (i!=lca) { ans-=sum[ i]; i-=C(i);}
return ans;
}
【有没有觉得很厉害！！！】
然后我介绍一下如何将a钟某一个元素变为原来的几倍或几分之一。
假如我现在想把a[ i]除以2
那么如果直接对树状数组中所有包含a[ i]的sum除以2，由于取整的原因会造成不连续，但我们如果用倒序修改的方式就能完美解决此问题。
void enlarge(int x){
for (int i=n;i>=1;i--) change(i,-getval(i)/2);
}
现在对于一维的树状数组应该很清楚了，那二维数组呢？
我们可以将sum定义为sum[ x][ y]=Σ(i=x-C(x)+1,x,Σ(j=y-C(y)+1,y,a[ i][ j]))
那么代码就很简单了
int query2d(int x,int y){
int ans=0;
while (x>0) {
int ty=y;
while (ty>0){
ans+=sum[ x][ ty];
ty-=C(ty);
}
x-=C(x);
}
return ans;
}
void change2d(int x,int y,int delta){
while (x<=n){
int ty=y;
while (ty<=n){
sum[ x][ ty]+=delta;
ty+=C(ty);
}
x+=C(x);
}
}
同理，我们也可以扩展到n维，我就不详细写了。
速度对比：
对一个大小为10000000的数组随机进行1000次修改，进行100次求和操作用时：
普通数组：
树状数组：
速度悬殊如此巨大
例题：逆序对
给定一个数组a,求数组a中逆序对的数量，其中逆序对(i,j)满足1<=i<j<=n,a[ i]>a[ j]。
#include<iostream>
using namespace std;
typedef long long ll;
struct node {
ll v;
int d;
node(){
v=d=0;
}
};
int n;
node a[ 100001];
int sum[ 100001];
int c[ 100001];
inline int lb(int x){ //lowbit
return x&(-x);
}
void qs(int l,int r){ //快速排序
int i=l,j=r,mid=a[ (l+r)/2].v;
do {
while (a[ i].v<mid) i++;
while (a[ j].v>mid) j--;
if (i<=j){
node mm=a[ i];
a[ i]=a[ j];
a[ j]=mm;
i++,j--;
}
}while (i<=j);
if (i>l) qs(i,r);
if (j<r) qs(l,j);
}
ll query(int x){
ll ans=0;
while (x>0){
ans+=sum[ x];
x-=lb(x);
}
return ans;
}
void insert(int x){
while (x<=n){
sum[ x]++;
x+=lb(x);
}
return ;
}
int main(){
ios::sync_with_stdio(false); //此句话可加快iostream的速度
cin>>n;
for (int i=1;i<=n;i++){
cin>>a[ i].v;
a[ i].d=i;
}
qs(1,n);
int last=-1,temp=-1,k=0;
for (int i=1;i<=n;i++){
temp=a[ i].v;
if (temp!=last){
last=temp;
k++;
}
c[ a[ i].d]=k;
}
ll s=0;
for (int i=n;i>=1;i--){
insert(c[ i]);
s+=query(c[ i]-1);
}
cout<<s;
return 0;
}
最后，万恶的论坛编辑器代码全都是用方括号括起来的，害得我不能直接用[ ]将下标括起来，否则就直接识别成格式了。。。而我又需要一些格式比如表个啥的，编辑器代码禁用了不行，不禁用也不行。。。真是，，鱼和熊掌不可兼得。。于是机制的我发现给[ ]里的东西加个空格就不会识别成编辑器代码了哈哈哈哈哈哈哈
最重要的事情：你看懂学会了技能get提升了，让我的吾爱币、热心值也提升一下子呗~~（反正评分又不会消耗你的）
hez2010 发表于 2016-10-31 09:58
不用树状数组，k的前缀和（也就是1~k）是a[ 1] ... a[ k]；用了树状数组以后是query(k)
谢谢楼主分享 誓言伤痕 发表于 2016-10-31 02:15
前缀和怎么算的？
不用树状数组，k的前缀和（也就是1~k）是a[ 1]+...+a[ k]；用了树状数组以后是query(k) 支持，LZ这样的教学贴简直是版块的一股清流 表示只看了开头就不想看了，多维数组分分钟要我命！ qq20036 发表于 2016-10-30 19:17
表示只看了开头就不想看了，多维数组分分钟要我命！
你仔细看，是一维的数组 {:1_921:}{:1_921:}eeeeee 先占个沙发！ 支持楼主，希望楼主多多更新 希望楼主多多更新 本帖最后由 pengxs 于 2016-10-30 22:54 编辑
好帖，楼主多多更新 厉害 这样不错的
页:
[1]
2