307. Range Sum Query - Mutable

Question

Given an integer array nums, find the sum of the elements between indices i 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

Thinking:

  • Method 1: 通过数组存储数据。
class NumArray {
    private int[] nums;
    public NumArray(int[] nums) {
        this.nums = nums;
    }

    public void update(int i, int val) {
        nums[i] = val;
    }

    public int sumRange(int i, int j) {
        int sum = 0;
        for(; i <= j; i++)
            sum += this.nums[i];
        return sum;
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */
  • Method 2: 保存从0加到当前数的和
class NumArray {
    private int[] sum;
    public NumArray(int[] nums) {
        this.sum = new int[nums.length];
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            count += nums[i];
            sum[i] = count;
        }
    }

    public void update(int i, int val) {
        int old = i > 0? (sum[i] - sum[i - 1]): sum[0];
        int diff = val - old;
        for(int j = i; j < sum.length; j++){
            sum[j] += diff;
        }
    }

    public int sumRange(int i, int j) {
        if(i == 0) return sum[j];
        else
            return sum[j] - sum[i - 1];
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */

Second time

  1. Use binary index tree 
    class NumArray {
 private int[] c;
 private int[] nums;
 private int lowBit(int n){
     return n & (-n);
 }
 public NumArray(int[] nums) {
     c = new int[nums.length + 1];
     this.nums = nums;
     for(int i = 1; i <= nums.length; i++){
         int lowBit = lowBit(i);
         int sum = 0;
         for(int j = i - lowBit + 1; j <= i; j++){
             sum += nums[j - 1];
         }
         c[i] = sum;
     }
 }
 public void update(int i, int val) {
     int diff = val - nums[i];
     nums[i] = val;
     int index = i + 1;
     while(index <= this.nums.length){
         c[index] += diff;
         index += lowBit(index);
     }
 }
 public int sumRange(int i, int j) {
     int sum1 = 0;
     int index1 = i;
     while(index1 > 0){
         sum1 += c[index1];
         index1 -= lowBit(index1);
     }
     int sum2 = 0;
     int index2 = j + 1;
     while(index2 > 0){
         sum2 += c[index2];
         index2 -= lowBit(index2);
     }
     return sum2 - sum1;
 }
}
/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */
  2. Use segment tree to solve this question. 
    class NumArray {
 private int[] segment;
 private int[] nums;
 public NumArray(int[] nums) {
     this.segment = new int[nums.length << 2 + 1];
     this.nums = nums;
     if(nums != null && nums.length != 0)    build(1, nums.length, 1);
 }
 private void build(int l, int r, int k){
     if(l == r){
         segment[k] = this.nums[l - 1];
     }else{
         int m = l + ((r - l) >> 1);
         build(l, m, k << 1);
         build(m + 1, r, k << 1 | 1);
         segment[k] = segment[k << 1] + segment[k << 1 | 1];
     }
 }
 public void update(int i, int val) {
     update(i + 1, val - this.nums[i], 1, this.nums.length, 1);
     this.nums[i] = val;
 }
 private void update(int i, int diff, int l, int r, int k){
     if(l == r) segment[k] += diff;
     else{
         int mid = l + ((r - l) >> 1);
         if(i <= mid)    update(i, diff, l, mid, k << 1);
         else    update(i, diff, mid + 1, r, k << 1 | 1);
         segment[k] = segment[k << 1] + segment[k << 1 | 1];
     }
 }
 public int sumRange(int i, int j) {
     return sum(i + 1, j + 1, 1, this.nums.length, 1);
 }
 private int sum(int L, int R, int l, int r, int k){
     if(L <= l && R >= r) return segment[k];
     else{
         int m = l + ((r - l) >> 1);
         int sum = 0;
         if(L <= m) sum += sum(L, R, l, m, k << 1);
         if(R > m) sum += sum(L, R, m + 1, r, k << 1 | 1);
         return sum;
     }
 }
}
/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */

Third time

  1. BIT ```Java class NumArray { private int[] nums; private int[] bit;

    private int lowBit(int x){ return x & (-x); } public NumArray(int[] nums) { this.nums = new int[nums.length + 1]; for(int i = 0; i < nums.length; i++){ this.nums[i + 1] = nums[i]; } this.bit = new int[nums.length + 1]; for(int i = 1; i < this.nums.length; i++){ for(int j = i - lowBit(i) + 1; j <= i; j++) this.bit[i] += this.nums[j]; } }

    public void update(int i, int val) { int diff = val - nums[i + 1]; nums[i + 1] = val; int index = i + 1; while(index < nums.length){ bit[index] += diff; index += lowBit(index); } }

    private int sum(int i){ int sum = 0; while(i > 0){ sum += bit[i]; i -= lowBit(i); } return sum; }
    public int sumRange(int i, int j) { return sum(j + 1) - sum(i); } }

/**

  • Your NumArray object will be instantiated and called as such:
  • NumArray obj = new NumArray(nums);
  • obj.update(i,val);
  • int param_2 = obj.sumRange(i,j); */ ```

  1. Segment Tree ```Java class NumArray { private int[] nums; private int[] segment; public NumArray(int[] nums) { if(nums == null || nums.length == 0) return; this.nums = nums; this.segment = new int[nums.length « 2 + 1]; insert(1, nums.length, 1); } private void insert(int l, int r, int k){ if(l == r) segment[k] = nums[l - 1]; else{ int m = l + ((r - l) » 1); insert(l, m, k « 1); insert(m + 1, r, k « 1 | 1); segment[k] = segment[k « 1] + segment[k « 1 | 1]; } }

    public void update(int i, int val) { update(i, val - nums[i], 1, nums.length, 1); this.nums[i] = val; } private void update(int i, int diff, int l, int r, int k){ if(l == r) segment[k] += diff; else{ int m = l + ((r - l) » 1); if((i + 1) <= m) update(i, diff, l, m, k « 1); if((i + 1) > m) update(i , diff, m + 1, r, k « 1 | 1); segment[k] = segment[k « 1] + segment[k « 1 | 1]; } }

    public int sumRange(int i, int j) { return sumRange(i + 1, j + 1, 1, this.nums.length, 1); } private int sumRange(int L, int R, int l, int r, int k){ if(l >= L && r <= R) return segment[k]; else{ int m = l + ((r - l) » 1); int sum = 0; if(L <= m) sum += sumRange(L, R, l, m, k « 1); if(R > m) sum += sumRange(L, R, m + 1, r, k « 1 | 1); return sum; } } }

/**

  • Your NumArray object will be instantiated and called as such:
  • NumArray obj = new NumArray(nums);
  • obj.update(i,val);
  • int param_2 = obj.sumRange(i,j); */ ```