首页 > 代码库 > 树状数组
树状数组
看到树状数组后觉得这个数据结构很优美，比较有意思，虽然很多时候线段树能做，但树状数组内存消耗更小，思想也很有意思，就想记录一下
看上去是比较漂亮的，A[] 是序列的实际数值， C[] 记录的是某一段A[]的和，例如 C[4]就是 sun(1--4)。
先介绍个很关键的函数：int lowbit(int x){return x&(-x);} 这个可以返回二进制数 x 中最低位的 1 还是 1 ，其余都为 0 的数,比如对于 1000(8的二进制) 1000=100+lowbit(100)=110+lowbit(110)=111+lowbit(111);
其实 C[i] 有很多性质:
1，将 i 化为二进制，比如 i = 6 = 110 那么 lowbit(6) = 2 ，代表 C[6] 记录了 2 个数的和, lowbit(7)=1 ,所以 C[7] 记录的 1 个数的和
2，C[i]的父节点是 C[i+lowbit(i)]
看懂了这些再看看代码，很容易理解了
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 5 using namespace std; 6 #define MAXN 1000 7 8 int n; 9 int A[MAXN];10 int C[MAXN];11 12 int lowbit(int x)13 {14 return x&(-x);15 }16 17 void new_tree(int n) // 建树 大概 n*log(n)18 {19 memset(C,0,sizeof(C));20 for (int i=1;i<=n;i++)21 {22 C[i]+=A[i];23 for (int j=i+lowbit(i);j<=n;j+=lowbit(j)) //性质224 C[j]+=A[i];25 }26 }27 28 void update(int x,int add) //A[x]增减29 {30 A[x]+=add;31 while (x<=n)32 {33 C[x]+=add;34 x+=lowbit(x);35 }36 }37 38 int getsum(int x)//[1--x]的和39 {40 int sum=0;41 while(x>0)42 {43 sum+=C[x];44 x -= lowbit(x); //性质145 }46 return sum;47 }48 49 int main()50 {51 scanf("%d",&n);52 for (int i=1;i<=n;i++)53 scanf("%d",&A[i]);54 new_tree(n);55 56 int l,r;57 scanf("%d %d",&l,&r);58 printf("%d\n",getsum(r)-getsum(l-1)); //l--r 的和59 60 return 0;61 }
还可以升级到多维的，很厉害
树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。