树状数组适合类型：

区间查询和单点修改，都为log(n)复杂度

希望得到有序map中新插入元素的rank

如果原数组长度为n,那么树状数组长度为n+1
两个操作:
(1)query(i+1),结果为数组下标【0，i】的前缀和
(2)add(int x,int u),给数组下标为x-1的值加u
题目链接：
https://leetcode.cn/problems/range-sum-query-mutable/
板子：

class NumArray {
public:
vector<int> tree;
int lowbit(int x) {
return x & -x;
}
int query(int x) {
int ans = 0;
for(int i = x; i > 0; i -= lowbit(i))
ans += tree[i];
return ans;
}
void add(int x, int u) {
for(int i = x; i <= n; i += lowbit(i))
tree[i] += u;
}
vector<int> nums;
int n;
NumArray(vector<int>& nums) {
this->nums = nums;
n = nums.size();
tree.resize(n+1, 0);
for(int i = 0; i < n; i++)
add(i+1, nums[i]);
}
void update(int index, int val) {
add(index+1, val-nums[index]);
nums[index] = val;
}
int sumRange(int left, int right) {
return query(right+1) - query(left);
}
};

最后

以上就是彪壮未来为你收集整理的C++树状数组板子区间查询和单点修改，都为log(n)复杂度希望得到有序map中新插入元素的rank的全部内容，希望文章能够帮你解决C++树状数组板子区间查询和单点修改，都为log(n)复杂度希望得到有序map中新插入元素的rank所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。