LeetCode *** 307. Range Sum Query - Mutable (Binary Indexed Trees)

本文主要是介绍LeetCode *** 307. Range Sum Query - Mutable (Binary Indexed Trees)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

Given an integer array nums, find the sum of the elements between indicesi and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

1. The array is only modifiable by the update function.
2. You may assume the number of calls to update and sumRange function is distributed evenly.

分析：

代码：

class NumArray {
public:vector<int> record, tree;NumArray(vector<int> &nums) {int size = nums.size(), idx;record = nums;record.insert(record.begin(), 0);tree = vector<int>(size + 1, 0);for (int i = 1; i <= size; ++i) {idx = i - (i&-i) + 1;for (int j = idx; j <= i; ++j)tree[i] += record[j];}}void update(int i, int val) {int differ = val- record[i + 1], idx = i + 1;record[i + 1] = val;while (idx<record.size()) {tree[idx] += differ;idx += (idx&-idx);}}int sumRange(int i, int j) {int sum1 = 0,sum2=0, idx = i,jdx=j+1;while (idx>0||jdx>0) {if (idx > 0) {sum1 += tree[idx];idx -= (idx&-idx);}if (jdx > 0) {sum2 += tree[jdx];jdx -= (jdx&-jdx);}}return sum2-sum1;}
};

这篇关于LeetCode *** 307. Range Sum Query - Mutable (Binary Indexed Trees)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---