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

前言

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

树状数组的英文名称是 ‌Binary Indexed Tree‌，缩写为 ‌BIT‌。我习惯翻译成TreeArr。

最常见的应用

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

树状数组的用途

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

基础操作

一，求前缀和。即 ∑ j : 0 i a [ j ] \sum_{j:0}^ia[j] ∑j:0i​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<classELE=int>classCTreeArrAddOpe:publicITreeArrSumOpe<ELE>{public:virtualvoidAssign(ELE& dest,const ELE& src){ dest += src;}virtual ELE Back(const ELE& n1,const ELE& n2){return n1 - n2;}};template<classELE=int,classELEOpe= CTreeArrAddOpe<ELE>>classCTreeArr{public:CTreeArr(int iSize):m_vData(iSize +1){}voidAdd(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(){returnSum(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<classELE=int>classCTreeArrXorOpe:publicITreeArrSumOpe<ELE>{public:virtualvoidAssign(ELE& dest,const ELE& src){ dest ^= src;}virtual ELE Back(const ELE& n1,const ELE& n2){return n1 ^ n2;}};template<classELE=int>classCTreeArrXor:publicCTreeArr<ELE,CTreeArrXorOpe<ELE>>{public:using CTreeArr<ELE, CTreeArrXorOpe<ELE>>::CTreeArr;};

动态开点树状数组

template<classELE=int,classELEOpe= CTreeArrAddOpe<ELE>>classCTreeArrMap{public:CTreeArrMap(longlong llMin,longlong llMax):m_llMin(llMin),m_llMax(llMax){}voidAdd(longlong 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(longlong index)//[0...index]之和{if((index < m_llMin)||(index > m_llMax)){return0;} index = index - m_llMin +1; ELE ret =0;while(index){ m_ope.Assign(ret, m_vData[index]); index -= index &(-index);}return ret;} ELE Sum(){returnSum(m_llMax - m_llMin +1);} ELE Get(longlong index){return m_ope.Back(Sum(index),Sum(index -1));}private: ELEOpe m_ope; unordered_map <longlong, ELE> m_vData;constlonglong m_llMin, m_llMax;};

最值树状数组

template<classT=int,T def = INT_MIN>classCTreeArrMax{public:CTreeArrMax(int iEleSize):m_iMax(iEleSize){ m_aMax.assign(iEleSize +1, def); m_aRangMax.assign(iEleSize +1, def);}voidModify(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){constint 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:intBitLower(int x){return x &(-x);}constint m_iMax; vector<T> m_aMax, m_aRangMax;};template<classT=int, T def = INT_MAX>classCTreeArrMin{public:CTreeArrMin(int iEleSize):m_max(iEleSize){}voidModify(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<longlong, LLONG_MAX> CTreeArrLLMin;

和差分数组结合

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

树状数组使用样例

力扣

洛谷

扩展阅读

视频课程

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

测试环境

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