数状数组的学习总结-白红宇

数状数组的学习总结

阅读量：6236 次

发布时间：2019-06-22

本文共 3495 字，大约阅读时间需要 11 分钟。

一个小小的树状数组竟然让我纠结到现在。从开始着手到现在能理解一个很重要的函数，一共花了大概5个小时。这样看来，时间也不算多嘛！@_@……呵呵！

我深刻的感觉到一个知识点是否容易领悟在于找到好的学习资料。如果我一直抱着手头的那几张PPT，和topcoder网站上的那个网页，我肯定到现在都无法理解出来。

总结一下学习的过程吧！毕竟任何一个没有良好的过程的成功是很难复制的。

刚开始看电子科大的ppt，不懂，上网搜索到topcoder的网页，再看依然不懂，接着搜索网页，看，还是不懂。其间，还搜索到一个求一组数第K大值的程序，贴出来吧

/**********************************

树状数组实现查找K小的元素

经典。

限制：数据范围在1<<20 以内

***********************************/

#include <iostream>

using

namespace std;

#define maxn 1<<20

int n,k;

int c[maxn];

int

lowbit(

int x){

return x&-x;

}

void

insert(

int x,

int t){

while(x<maxn){

c[x]+=t;

x+=lowbit(x);

}

int

find(

int k){

int cnt=0,ans=0;

for(

int i=20;i>=0;i--){

ans+=(1<<i);

if(ans>=maxn || cnt+c[ans]>=k)ans-=(1<<i);

else cnt+=c[ans];

}

return ans+1;

}

void

input(){

memset(c,0,

sizeof(c));

int t;

scanf("%d%d",&n,&k);

for(

int i=0;i<n;i++){

scanf("%d",&t);

insert(t,1);

}

printf("%d\n",find(k));

}

int

main(){

int cases;

cout<<"1<<20="<<(1<<20)<<endl;

scanf("%d",&cases);

while(cases--){

input();

}

return 0;

}

这个程序首先需要输入程序查找的次数。随便输入1就可以了。然后呢，输入源数组的大小及第K小数的K值，比如，我要在长度为10的数组中查询第4小的数据，则输入10 4。

接下来呢，需要输入10个值了，这对应着数组中的值。比如：0，1，2，3，4，5，6，7，8，9。剩下的事情就交给程序了。对于上面的数据，她会输出3。

但是这个程序我依然没理解到树状数组的思想。只能说我太笨了……接着研究呗！

我想是否结合实际的例子会有效一些？就分别试了poj上的两个题，一个是题id=2352 star另一个是id=3321的 apple tree。Apple tree 是找到源代码就放弃了。因为觉得太难了。Star直接就没找源代码。

鬼使神差的，我又去找博客了。

看到了 (搞懂树状数组)。觉得隐隐约约像找到门口了。看了一下，还是不怎么理解，那时，就已经准备放弃了。想应该先看线段树的。不知怎么的，又不甘心，回来了。在本子上写了一下add()函数中tree数组下标的递推关系（如：tree[1] à tree[2] à tree[4] à tree[8]），然后再结合那个博客，就把add()函数弄清楚了。先贴代码吧！

#include<iostream>

using

namespace std;

int tree[17];//其实只有16个数，因为0位不用

int n=16;

int

lowbit(

int x){

return x&-x;

}

void

add(

int k,

int& num){

while(k<=n)

{

tree[k]+=num;

cout<<"k="<<k<<endl;

cout<<"tree[k]="<<tree[k]<<endl;

cout<<"num="<<num<<endl;

k+=k&-k;//其实，这行代码换成k+=lowbit(k);是一样的

}

int

main(){

int a[17]={0,1, 0, 2, 1, 1, 3, 0, 4, 2, 5, 2, 2, 3, 1, 0, 2};

memset(tree,0,

sizeof(tree));

for(

int i=1;i<=n;i++){

add(i,a[i]);

}

cout<<tree[16]<<endl;//tree[16]中保存是的所有数据的和

return 0;

}

Basic idea

Each integer can be represented as sum of powers of two. In the same way, cumulative frequency can be represented as sum of sets of subfrequencies. In our case, each set contains some successive number of non-overlapping frequencies.

idx is some index of

BIT.

r is a position in

idx of the last digit 1 (from left to right) in binary notation.

tree[idx] is sum of frequencies from index (

idx - 2^

r + 1) to index

idx (look at the Table 1.1 for clarification). We also write that

idx is

responsible for indexes from (

idx - 2^

r + 1) to