树状数组

1. 定义

给定序列（数列）A，我们设一个数组C满足C[i] = A[i–2^k+ 1] + … + A[i]，其中，k为i在二进制下末尾0的个数，i从1开始算，则称C为树状数组（二进制索引树）。

对于给定的i，有三种求解方法：

(1) 2^k= i&(i^(i-1))

(2) 2^k= i^(i&(i-1))

(3) 2^k= i & (-i)   (补码性质)

2. 用途

快速地获取连续几个数的和、动态地修改一些位置上的数字。

注：如果我们用一个数组B[i]记录A中前i项和，查询的时间代价是O(1)，但是在更新每一个元素时时间代价为O(n)，而采用树状数组时间代价O(log₂n)。

3. 操作

3.1 求树状数组C

方法一：根据公式C[i] = A[i–2^k+ 1] + … + A[i]可以轻松的计算出数组C中的每一个元素。

方法二：初始化数组A与数组C为0，然后更新A中的每个元素为目标元素，即我们要用于查询部分和的数据。当更新A[i]时，采用自底向上的方式更新每一个包含A[i]的树状数组C的值。易得直接包含A[i]的为C[i]，直接包含C[i]的为C[i+2^k]，其中k为i的二进制表示中0的个数，求解方法见定义。

方法一与方法二的时间复杂度分别为O(n²)与O(nlog₂n)，其中n为原始数据个数。

3.2 查询

我们将查询分为两部分：从起点开始的连续i个数的和与连续区间[k,m]之和。用sum[i]代表从起点开始连续i个数之和。

查询一：从起点开始的连续i个数

sum[i]包含了i项，而C[i]包含了从i开始向前数共2^k项，因此我们有sum[i] = C[i] + sum[i-2^k](sum[0] = 0)。而k代表了i的二进制表示中0的个数，i-2^k表示将i中最后一个1置0，因此该递归式递归次数为i中1的个数，即log₂i。可得查询操作的时间复杂度为log₂n，其中n为原始数据个数。

注：i-2^k =i&(i-1)

查询二：连续区间[k, m]数字之和S

因为S = sum[m] – sum[k-1]，因此第二种查询可以转化为第一种查询。该计算方式进行了两次查询一，因此时间复杂度也为log₂n。

3.3 修改元素的值

对元素的修改包括值的增加、减少与改变，而减少一个值可以理解为增加一个负值，改变也可以转变为增加一个值（或正或负），因此这里指描述增加即可。

3.3.1 增加

设对A[i]元素增加k：

(1) C[i] = C[i]+ k

(2) i = i+ 2^k，如果i<n，执行(1)；反之，运算结束。

该操作的时间复杂度为O(log₂n)。

3.4 增加元素个数

相比于线段树来说，块状数组可以增加元素的个数，而不需要从新计算已经求出来的数据。

4. 代码实现

#include <iostream>
#include <assert.h>
using namespace std;
#define MAXNUM 10

template<class T>
class CTreeArry
{
public:
	CTreeArry(int num);
	~CTreeArry();

private:
	int dataNum;

public:
	T *sourceData;
	T *treeArry;
	void Init(const T arry[], int n);
	void Increase(const int i, const T value);
	void Reduce(const int i, const T value);
	void Change(const int i, const T value);
	T Query(const int end);
	T Query(const int start, const int end);

	void AddNumOfElem(const T arry[], int addNum);
	void upData(const int i, const T value);
};

template<class T>
CTreeArry<T>::CTreeArry(int num)
	:dataNum(num)
{
	sourceData = new T[num+1];
	treeArry = new T[num+1];

	memset(sourceData, 0, sizeof(T)*(dataNum+1));
	memset(treeArry, 0, sizeof(T)*(dataNum+1));

}

template<class T>
CTreeArry<T>::~CTreeArry()
{
	delete []sourceData;
	delete []treeArry;
}


template<class T>
void CTreeArry<T>::Init(const T arry[], int n)
{
	for (int i=1; i<=n; ++i)
	{
		Increase(i, arry[i]);
	}
}


template<class T>
void CTreeArry<T>::Increase(const int i, const T value)
{
	assert(i>=1 && i<=dataNum);
	int temp = i;
	sourceData[temp] += value;

	for (; temp<=dataNum; temp += (temp&(-temp)))
	{
		treeArry[temp] += value;
	}

}

template<class T>
void CTreeArry<T>::Reduce(const int i, const T value)
{
	assert(i>=1 && i<=dataNum);
	Increase(i, -value);
}

template<class T>
void CTreeArry<T>::Change(const int i, const T value)
{
	assert(i>=1 && i<=dataNum);
	Increase(i, value-sourceData[i]);
}

template<class T>
T CTreeArry<T>::Query(const int end)
{
	assert(end>=1 && end<=dataNum);

	T sum = 0;
	//下面两个等价
//	for (int i=end; i>0; i-=(i&(-i)))
	for (int i=end; i>0; i=i&(i-1))
	{
		sum += treeArry[i];
	}
	return sum;
}

template<class T>
T CTreeArry<T>::Query(const int start, const int end)
{
	assert(start>=1 && start<=end && end<=dataNum);

	return Query(end) - Query(start-1);
}

template<class T>
void CTreeArry<T>::upData(const int i, const T value)
{
	assert(i>=1 && i<=dataNum);
	for (int j=i; j<=dataNum; j+=(j&(-j)))
	{
		treeArry[j] += value;
	}
}

template<class T>
void CTreeArry<T>::AddNumOfElem(const T arry[], int addNum)
{
	int tempDataNum = dataNum;
	dataNum = dataNum + addNum;
	T *tempSource = sourceData;
	T *tempTreeArry = treeArry;
	sourceData = new T[dataNum + 1];
	treeArry = new T[dataNum + 1];
	memset(sourceData, 0, sizeof(T)*(dataNum + 1));
	memset(treeArry, 0, sizeof(T)*(dataNum + 1));

	for (int i=1; i<=tempDataNum; ++i)
	{
		sourceData[i] = tempSource[i];
		if (i+(i&(-i))<=tempDataNum)
		{
			treeArry[i] = tempTreeArry[i];
		}
		else
		{
			upData(i, tempTreeArry[i]);
		}
	}
	delete tempSource;
	delete tempTreeArry;

	for (int i=tempDataNum+1; i<=dataNum; ++i)
	{
		Increase(i, arry[i-tempDataNum-1]);
	}
}

树状数组,布布扣,bubuko.com

树状数组

原文：http://blog.csdn.net/woniu317/article/details/24356473