本文主要是介绍[Algorithm] Binary Indexed Tree 树状数组模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、摘要
这是我个人的树状数组模板记录，对于其他人可能没有借鉴意义。
二、代码
// 树状数组类
// 下标从1开始
class BinaryIndexedTree{
public:// 构造函数，初始化数据数组c_，大小为总数据个数+1BinaryIndexedTree(int n){c_.resize(n+1);fill(c_.begin(), c_.end(), 0);}// 区间查询，查询a[1,idx]范围内的数据和int query(int idx){if(idx>=c_.size()){return 0;}int ret = 0;int i = idx;while(i>0){ret += c_[i];i -= lowBit(i);}return ret;}// 单点更新，将a[idx]数据增加num// 但是也可以达到区间修改的效果，即在c_中，将[idx,last)都增加numvoid update(int idx, int num){if(idx>=c_.size()){return;}int i = idx;while(i<c_.size()){c_[i] += num;i += lowBit(i);}}
private:// lowBit函数int lowBit(int num){return num&(-num);}vector<int> c_;
};
三、注意事项
- 树状数组得英文名字是Binary Indexed Tree；
- 数组分为原始数据数组a[]和前缀和数组c_[]，c_数组个数要比a数组多一个，因为c_从1开始计数；
- lowbit(x)函数为
return x&(-x);； - update(idx,val)为将c_[idx,idx+lowbit(idx),…]增加val，即使a[]的后缀都增加val，更新下标时使用
i+=lowbit(i)； - query(idx)为求c_[idx,idx-lowbit(idx),…]，即求a得前缀和。更新下标时使用
i-=lowbit(i)；
这篇关于[Algorithm] Binary Indexed Tree 树状数组模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
