Range Sum Query - Mutable

• Lintcode : 840 / Leetcode : 307
• Level : Medium

Problem

Given an integer array nums, and then you need to implement two functions:

update(i, val) Modify the element whose index is i to val.
sumRange(l, r) Return the sum of elements whose indexes are in range of [l, r][l,r].
Example
Example 1:

Input: 
  nums = [1, 3, 5]
  sumRange(0, 2)
  update(1, 2)
  sumRange(0, 2)
Output:
  9
  8
Example 2:

Input:
  nums = [0, 9, 5, 7, 3]
  sumRange(4, 4)
  sumRange(2, 4)
  update(4, 5)
  update(1, 7)
  update(0, 8)
  sumRange(1, 2)
Output:
  3
  15
  12
Notice
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

Concept & Algorithm

1. 先用暴力破解
2. 再用binary index tree
   筆記

Time Complexity & Space Complexity

sol 1:

time : O(n)
space: O(n)

sol 2:

time : O(logn)
space: O(n)

Answer

// sol 1:
class NumArray {
    vector<int> prefix;
    vector<int> origin;
public:
    NumArray(vector<int> nums) {
        origin = nums;
        vector<int> p(nums.size() + 1);
        p[0] = 0;
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            p[i + 1] = sum;
        }
        prefix = p;
    }

    void update(int i, int val) {
        int diff = val - origin[i];
        origin[i] += diff;
        for (int j = i + 1; j <= origin.size(); j++){
            prefix[j] += diff;
        }

    }

    int sumRange(int i, int j) {
        return prefix[j + 1] - prefix[i];
    }
};


// sol 2:
class NumArray {
    int n;
    vector<int> bit;
    vector<int> arr;

public:
    NumArray(vector<int>& nums) : n(nums.size()), bit(n + 1, 0), arr(n, 0) {
        for (int i = 0; i < nums.size(); i++) {
            update(i, nums[i]);
        }
    }
    void update(int i, int val) {
        int diff = val - arr[i];
        int j = i + 1;
        while (j < bit.size()) {
            bit[j] += diff;
            j += lowbit(j);
        }
        arr[i] = val;
    }

    int sumRange(int i, int j) {
        return query(j + 1) - query(i);
    }
    // prfix sum : 0 ~ i
    int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += bit[i];
            i -= lowbit(i);
        }
        return sum;
    }
    int lowbit(int x) {
        return x & (-x);
    }

};

tags: binary index tree

​