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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| // @lc code=start
/// 树状数组
struct NumArray {
lowbit_sums: Vec<i32>, //按lowbit方式存储的sum数组
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl NumArray {
/// 新建树状数组
fn new(nums: Vec<i32>) -> Self {
let mut na = NumArray {
lowbit_sums: vec![0; nums.len()], // lowbit_sums数组
};
for i in 0..nums.len() {
na.modify((i as i32), nums[i]);
}
na
}
/// 修改nums[i]值
fn modify(&mut self, i: i32, diff: i32) {
let mut i = i + 1; // 树状数组下标=原数组下标+1
//自底向上修改树状数组相关节点
while i <= self.lowbit_sums.len() as i32 {
self.lowbit_sums[(i-1) as usize] += diff;
i += NumArray::lowbit(i);
}
}
/// 查询前缀和sum(nums[..i]), 区间范围: [0, i)
fn get_prefix_sum(&self, i: i32) -> i32 {
let mut res = 0;
let mut i = i + 1; // 树状数组下标=原数组下标+1
//自顶向下依次计算树状数组节点和
while i > 0 {
res += self.lowbit_sums[(i-1) as usize];
i -= NumArray::lowbit(i);
}
res
}
/// 查询nums[i]
fn get(&self, i: i32) -> i32 {
self.get_prefix_sum(i) - self.get_prefix_sum(i-1)
}
/// 更新nums[index]值
fn update(&mut self, i: i32, val: i32) {
let diff = val - self.get(i);
self.modify(i, diff)
}
/// 查询区间和sum(nums[left..right]), [left, right)
fn sum_range(&self, left: i32, right: i32) -> i32 {
// 区间和转化为前缀和之差
self.get_prefix_sum(right) - self.get_prefix_sum(left-1)
}
/// 截取x的最低位1开始后的尾部
fn lowbit(x: i32) -> i32 {
x & -x
}
}
/**
* Your NumArray object will be instantiated and called as such:
* let obj = NumArray::new(nums);
* obj.update(index, val);
* let ret_2: i32 = obj.sum_range(left, right);
*/
// @lc code=end
|