c/c++树状数组

今天在看程序竞赛的书，看到一段代码，是说树状数组的，书上讲得不怎么清楚，

 

自己也不是很理解，只知道可以这样用，但怎么构造成一个树就不是很明白了，希望大家指点一下。

 

数组：c[MAX]；

函数：lowbit(int),insert(int),getsum(int);

 

代码如下：

 

#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;

const int MAX = 1000;

int c[MAX];

int lowbit(int a){
	return a & -a;
}

void insert(int a,int d,int max){
	while(a<=max){
		c[a] += d;
		a += lowbit(a);     //不是很明白这样做的意思
	}
}

long getsum(int a){
	int t = 0;
	while(a > 0){
		t += c[a];
		a -= lowbit(a);
	}
	return t;
}

int main(){
	ifstream cin("E:\\test.txt");

	memset(c , 0 , sizeof(c));

	int n ,i;
	cin>>n;

	for(i=1; i<=n ; i++){
		insert(i,1,n);
	}

	insert(5,-2,n);
	
	for(i=1; i<=n ; i++){
		printf("%d ",getsum(i));
	}

	printf("\n");

	return 0;
}

 

void insert(int a,int d,int max){ 
    while(a<=max){ 
        c[a] += d; 
        a += lowbit(a);     //不是很明白这样做的意思 
    } 
} 

a += lowbit(a);查找父结点,跟新父结点的值,直到a <=max为止,c就是一个树状数组

我也大概明白是更新父节点的值，但不是很明白，为什么用lowbit就能构造成一棵树？求实现原理呀~