【C++】树状数组的使用、原理、封装类、样例

前言

本博文代码打包下载
C++算法与数据结构分类汇总

最常见的应用

有序集合包括若干整数,求小于x的数量。auto it = s.lower(x) , it - s.begin()，这个时间复杂度是O(n)。
由于查询和插入交替进行，故不能用向量。

树状数组的用途

令原始数组是a，长度为n。

基础操作

一，求前缀和。即${\sum }_{j:0}^{i}a[j]$。时间复杂度：O(logn)。
二，a[i] +=x。时间复杂度：O(logn)

组合操作

区间和：两个前缀和相减便是区间和，a[i…j]之和=a[0…j]之和-a[0…i-1]之和。
求a[i]的值：即区间a[i…i]之和。
a[i]=x： y=a[i]的值，a[i] += (x-y)

树状数组的原理

性质一，下标从1开始。
性质二，f(x)= x&(x-1) ，即将最低位的1变成0，f(6)=4。data[i]=a[f(i) + 1] 到a[i]之和。故a[1…i] 之和等于按以下方式迭代的a[i]之和:i = f(i)。
性质三,g(i)=x&(-x)即最低位1的值，f(6)=2。a[i]+= x，等于data[i]+=x，按如下方式迭代i: i +g(x)。
性质四：f(i)最低位1后面的任意一个0变成1，一定是对应i。且不存在其它方式产生对应的i。
性质五：f(j) < i <= j， f(j)中1的个数不会多于f(i)。如果f(j)小于f(i)，根据性质四无法让j >=i。令f(j)的第k3位小于f(i)，如果有多个k3，取最高位。不修改k3或更高位，无法大于等于i。
如果f(j)>f(i),说明i的最低位1后面有1，根据性质四，无法如何j都不会大于i。
令i的最后一个1是第k4位，只讨论比k4高的位，f(j)<=i，否则整个f(j)>i。比k4高的位f(i)等于i，故f(j)和f(i)k4为之前部分相等。f(j)>f(i)，故必须比k4低的位有1。
性质六：如果f(j)有k个1，这k个1一定是f(i)的前k个1。证明同性质五。
如果f(j)有k个1，i从高位到低位第k个1是k1位，第k+1个1是k2位。 如果i有k+1个1.则j最后一个1为[k2，k1 - 1];否则j最后一个1为[k2 + 1, k1 - 1]。证明结束。

树状数组的封装类

静态开点求和和求异或和的树状数组。

template<class ELE = int >
class CTreeArrAddOpe:public ITreeArrSumOpe<ELE>
{
public:
	virtual void Assign(ELE& dest, const ELE& src) {
		dest += src;
	}
	virtual ELE Back(const ELE& n1, const ELE& n2) {
		return n1 - n2;
	}
};

template<class ELE = int,class ELEOpe = CTreeArrAddOpe<ELE> >
class CTreeArr
{
public:
	CTreeArr(int iSize) :m_vData(iSize + 1)
	{

	}
	void Add(int index, ELE value)
	{
		if ((index < 0) || (index >= m_vData.size() - 1)) { return; }
		index++;
		while (index < m_vData.size())
		{
			m_ope.Assign(m_vData[index], value);
			index += index & (-index);
		}
	}
	ELE Sum(int index)//[0...index]之和
	{
		index++;
		ELE ret = 0;
		while (index)
		{
			m_ope.Assign(ret, m_vData[index]);
			index -= index & (-index);
		}
		return ret;
	}
	ELE Sum() { return Sum(m_vData.size() - 2); }
	ELE Get(int index)
	{
		return m_ope.Back(Sum(index), Sum(index - 1));
	}	
private:
	ELEOpe m_ope;
	vector<ELE> m_vData;
};

template<class ELE = int >
class CTreeArrXorOpe : public ITreeArrSumOpe <ELE> {
public:
	virtual void Assign(ELE& dest, const ELE& src) {
		dest ^= src;
	}
	virtual ELE Back(const ELE& n1, const ELE& n2) {
		return n1 ^ n2;
	}
};

template<class ELE = int >
class CTreeArrXor : public CTreeArr<ELE, CTreeArrXorOpe<ELE>> {
public:
	using CTreeArr<ELE, CTreeArrXorOpe<ELE>>::CTreeArr;
};

动态开点树状数组

template<class ELE = int, class ELEOpe = CTreeArrAddOpe<ELE> >
class CTreeArrMap
{
public:
	CTreeArrMap(long long llMin, long long llMax) :m_llMin(llMin), m_llMax(llMax) {}
	void Add(long long index, ELE value)
	{
		if ((index < m_llMin) || (index > m_llMax)) { return; }
		index = index - m_llMin + 1;
		auto maxIndex = m_llMax - m_llMin + 1;
		while (index <= maxIndex)
		{
			m_ope.Assign(m_vData[index], value);
			index += index & (-index);
		}
	}
	ELE Sum(long long index)//[0...index]之和
	{
		if ((index < m_llMin) || (index > m_llMax)) { return 0; }
		index = index - m_llMin + 1;
		ELE ret = 0;
		while (index)
		{
			m_ope.Assign(ret, m_vData[index]);
			index -= index & (-index);
		}
		return ret;
	}
	ELE Sum() { return Sum(m_llMax - m_llMin + 1); }
	ELE Get(long long index)
	{
		return m_ope.Back(Sum(index), Sum(index - 1));
	}
private:
	ELEOpe m_ope;
	unordered_map <long long, ELE> m_vData;
	const long long m_llMin, m_llMax;
};

最值树状数组

template<class T = int,T def = INT_MIN>
class CTreeArrMax
{
public:
	CTreeArrMax(int iEleSize) :m_iMax(iEleSize) {
		m_aMax.assign(iEleSize + 1, def);
		m_aRangMax.assign(iEleSize + 1, def);
	}
	void Modify(int indexBase0, T value)
	{
		indexBase0++;
		if (value <= m_aMax[indexBase0])
		{
			return;
		}
		m_aMax[indexBase0] = value;
		while (indexBase0 <= m_iMax)
		{
			m_aRangMax[indexBase0] = max(m_aRangMax[indexBase0], value);
			indexBase0 += BitLower(indexBase0);
		}
	}
	T Query(int leftBas0, int rBase0)
	{
		leftBas0++;
		rBase0++;
		leftBas0 = max(1, leftBas0);
		rBase0 = min(m_iMax, rBase0);
		T iMax = def;
		while (rBase0 >= leftBas0)
		{
			const int pre = rBase0 - BitLower(rBase0);
			if (pre + 1 >= leftBas0)
			{
				iMax = max(iMax, m_aRangMax[rBase0]);
				rBase0 = pre;
			}
			else
			{
				iMax = max(iMax, m_aMax[rBase0]);
				rBase0--;
			}
		}
		return iMax;
	}
protected:
	int BitLower(int x)
	{
		return x & (-x);
	}
	const int m_iMax;
	vector<T> m_aMax, m_aRangMax;
};

template<class T = int, T def = INT_MAX>
class CTreeArrMin
{
public:
	CTreeArrMin(int iEleSize):m_max(iEleSize){}
	void Modify(int indexBase0, T value)
	{
		m_max.Modify(indexBase0, -value);
	}
	T Query(int leftBas0, int rBase0)
	{
		return -m_max.Query(leftBas0, rBase0);
	}
	CTreeArrMax<T, -def> m_max;
};

typedef CTreeArrMin<long long, LLONG_MAX> CTreeArrLLMin;

和差分数组结合

可以在O(logn)的时间内进行区间修改，在O(logn)的时间内进行单点查询。

树状数组使用样例

力扣

洛谷

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。