实用数据结构---树状数组（二叉索引树）

树状数组适用于动态连续和查询问题，就是给定一个区间，

查询某一段的和或者修改某一位置的值。

关于树状数组的结构请去百度百科,否则将看不懂下面内容

我们看这个题

士兵杀敌（二）

时间限制：1000 ms  |  内存限制：65535 KB 难度：5

描述

南将军手下有N个士兵，分别编号1到N，这些士兵的杀敌数都是已知的。

小工是南将军手下的军师，南将军经常想知道第m号到第n号士兵的总杀敌数，请你帮助小工来回答南将军吧。

南将军的某次询问之后士兵i可能又杀敌q人，之后南将军再询问的时候，需要考虑到新增的杀敌数。

输入

只有一组测试数据
第一行是两个整数N,M，其中N表示士兵的个数(1<N<1000000)，M表示指令的条数。(1<M<100000)
随后的一行是N个整数，ai表示第i号士兵杀敌数目。(0<=ai<=100)
随后的M行每行是一条指令，这条指令包含了一个字符串和两个整数，首先是一个字符串，如果是字符串QUERY则表示南将军进行了查询操作，后面的两个整数m,n，表示查询的起始与终止士兵编号；如果是字符串ADD则后面跟的两个整数I,A(1<=I<=N,1<=A<=100),表示第I个士兵新增杀敌数为A.

输出

对于每次查询，输出一个整数R表示第m号士兵到第n号士兵的总杀敌数，每组输出占一行

样例输入

5 6

1 2 3 4 5

QUERY 1 3

ADD 1 2

QUERY 1 3

ADD 2 3

QUERY 1 2

QUERY 1 5

样例输出

6

8

8

20

这就是典型的动态区间连续和查询问题。

树状数组需要三个函数

int lowBit(int x){
	return x&(-x);	//返回的值是2的k次幂，k为x二进制下从低位到高位0的个数
}
int sum(int n){
	int res = 0;
	while (n > 0){
		res += c[n];
		n -= lowBit(n);
	}
	return res;
}
void change(int i, int x, int n){
	if (i > n) return;
	c[i] += x;
	change(i + lowBit(i), x, n);
}

对于lowBit我解释一下，为什么是 x & -x，计算机里的整数采用补码表示
因此-x其实是按位取反，然后在末尾加1的结果，举个例子
32388 = 1001010110010000
-32388 = 0110101001110000
所以lowBit返回的值是x在二进制下从低位到高位最右面的1所对应的值
完整程序在下面

#include<stdio.h>
#define MAX_NUM 1000005
int a[MAX_NUM] = { 0 };
int c[MAX_NUM] = { 0 };
int lowBit(int x){
	return x&(-x);	//返回的值是2的k次幂，k为x二进制下从低位到高位0的个数
}
int sum(int n){
	int res = 0;
	while (n > 0){
		res += c[n];
		n -= lowBit(n);
	}
	return res;
}
void change(int i, int x, int n){
	if (i > n) return;
	c[i] += x;
	change(i + lowBit(i), x, n);
}
int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	int i;
	for (i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		if (i % 2 != 0)
			c[i] = a[i];
		else{
			int j;
			for (j = i - lowBit(i) + 1; j <= i; j++)
				c[i] += a[j];
		}
	}
	char order[10];
	int b, e, t = 0;
	for (i = 0; i < m; i++){
		scanf("%s", &order);
		scanf("%d%d", &b, &e);
		if (order[0] == 'Q'){
			printf("%d\n", sum(e) - sum(b - 1));
		}
		else{
			change(b, e, n);
		}
	}
	return 0;
}

实用数据结构---树状数组（二叉索引树）

原文：http://blog.csdn.net/u013174702/article/details/44007317