树状数组总结
问题：已知数组 a[],元素个数为n，现在更改数组中某些元素的值，求更改后a数组中i到j区间内元素的和（1<=i<=j<=n）。
对于这个问题我们当然可以用最朴素的方法来解决，从a[i]一直累加到a[j], 最坏的情况下复杂度为O(n)，对于m次更改和访问来说的复杂度就会为O(m*n)，当m和n较大时，复杂度就太大导致我们提交题目时就会TLE了，我们可以想一下，在元素发生改变的个数是比较少的，而我们却把所有的元素都进行了一遍计算，这样其实造成了很多无谓的运算，我们就可以把和分成一个个特定的小区间进行存储，从而减少再次运算时无谓的相加。但是如果我们存任意区间的和话，当n特别大的时候，存储量就会特别大，不易更改区间里的内容。我们整理一下思路，现在已经确定了要存储一些特定区间和的想法，但是不知具体该如何存储与操作。
如图；
因为1的二进制为1，所以c[1] = a[1]
因为2的二进制为10，所以才c[2] = a[1] + a[2];
以此类推，，，。
可以发现假设n用二进制表示时，从右数第一次出现1的位置为k;
则c[n] = a[n - k + 1] + a[n - k] + ...+ a[n];
当n是奇数的时候，二进制右边第一位是1，所以c[n] = a[n];
可以使用
int lowbit(int x)
{
return x & (-x);
}求 k
在C语言中
& 是 按位与运算符
-x 是x 的补码；补码为取反+1
x&(-x)返回x与2^64的最大公约数，即x最多能被n个2整除就返回2^n；如果x是奇数返回1
所以返回值为0，表示x=0
返回值为1，表示x为奇数
返回值为其他数，表示x为x与2^64的最大公约数
在条件语句中可以判断 该数是否为0，为1，能倍2整除？
利用状态位也可以 判断x是否为0
或者直接返回x与2^64的最大公约数
使用树状数组进行点求和的时候向后更新
void update(int position,int number)
{
for(int i = position;i <= n;i += lowbit(i))
c[i] += number;
}
向前求和
int get(int position)
{
int sum = 0;
for(int i = position;i >= 1;i -= lowbit(i))
sum += c[i];
return sum;
}
例如:HDU 1556
Color the ball
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6412 Accepted Submission(s):
3385
当N = 0，输入结束。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int map[100010];
int n;
int a,b;
int lowbit(int x)
{
return x & (-x);
}
void update(int position,int number)
{
for(int i = position;i <= n;i += lowbit(i))
map[i] += number;
}
int get(int position)
{
int sum = 0;
for(int i = position;i >= 1;i -= lowbit(i))
sum += map[i];
return sum;
}
int main()
{
printf("%d
",lowbit(6));
while(scanf("%d",&n),n != 0)
{
memset(map,0,sizeof(map));
for(int i = 1;i <= n;i ++)
{
scanf("%d%d",&a,&b);
update(a,1);update(b + 1,-1);
}
for(int i = 1;i < n;i ++)
printf("%d ",get(i));
printf("%d
",get(n));
}
return 0;
}