外包网站设计_宽带公司排名_免费seo网站优化工具_如何进行搜索引擎优化

前言

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

最常见的应用

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

树状数组的用途

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

基础操作

一，求前缀和。即 $\sum_{j:0}^ia[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)的时间内进行单点查询。

树状数组使用样例

力扣

	难度分
【C++二分查找树状数组】2424. 最长上传前缀	1604
【C++ 树状数组】2426. 满足不等式的数对数目	2030
【C++ 树状数组】1850. 邻位交换的最小次数	2073
【字符串】【贪心】【树状数组】2193. 得到回文串的最少操作次数	2090
【C++树状数组】3187. 数组中的峰值	2154
【树状数组】1649. 通过指令创建有序数组	2207
【树状数组一一映射】2179. 统计数组中好三元组数目	2272
【状态机dp 线段树树状数组】2407. 最长递增子序列 II	2280
【树状数组】2659. 将数组清空	2281
【树状数组队列】1505. 最多 K 次交换相邻数位后得到的最小整数	2336

洛谷

	难度等级
【树状数组 C++二分查找】P7333 [JRKSJ R1] JFCA	普及+
【前缀和前后缀分解树状数组】P9744 「KDOI-06-S」消除序列	普及+
【C++贪心树状数组】P8818 [CSP-S 2022] 策略游戏	普及+
【树状数组二分】P10235 [yLCPC2024] C. 舞萌基本练习	普及+
【树状数组】P5367康托展开	普及+
【树状数组贪心】P11453 [USACO24DEC] Deforestation S	普及+
【树状数组】P10673 【MX-S1-T2】催化剂	普及+
【树状数组排序双指针】P11048 [蓝桥杯 2024 省 Java B] 拼十字	普及+
【树状数组】P6278 [USACO20OPEN] Haircut G	普及+
【树状数组】P3608 [USACO17JAN] Balanced Photo G	普及+
【树状数组】P5200 [USACO19JAN] Sleepy Cow Sorting G	普及+
【树状数组位运算】P6225 [eJOI 2019] 异或橙子	普及+
【树状数组】P5459 [BJOI2016] 回转寿司	普及+
【树状数组】P5094 [USACO04OPEN] MooFest G 加强版	普及+
【差分数组树状数组】P5057 [CQOI2006] 简单题	普及+
【树状数组】P7629 [COCI 2011/2012 #1] SORT	普及+

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功

视频课程

先学简单的课程，请移步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++**实现。