C++树状数组板子区间查询和单点修改，都为log(n)复杂度希望得到有序map中新插入元素的rank

103 阅读 0 评论 68 点赞

我是靠谱客的博主彪壮未来，这篇文章主要介绍C++树状数组板子区间查询和单点修改，都为log(n)复杂度希望得到有序map中新插入元素的rank，现在分享给大家，希望可以做个参考。

树状数组适合类型：

区间查询和单点修改，都为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/
板子：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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);
}
};