307.Range-Sum-Query---Mutable

307. Range Sum Query Mutable

题目地址

https://leetcode.com/problems/range-sum-query-mutable/

题目描述

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

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

代码

Approach #1 FenwickTree (Binary indexed tree)

class NumArray {
    FenwickTree tree;
  int[] nums;
  public NumArray(int[] nums) {
        this.nums = nums;
    tree = new FenwickTree(nums.length);
    for (int i = 0; i < nums.length; i++) {
      tree.update(i + 1, nums[i]);
    }
  }

  public void update(int i, int val) {
        tree.update(i + 1, val - nums[i]);
    nums[i] = val;
  }

  public int sumRange(int i, int j) {
        return tree.query(j + 1) - tree.query(i);
  }
}

class FenwickTree {
    int sums[]; // 从 index = 1 开始
    public FenwickTree(int n) {
        sums = new int[n + 1];
    }

    public void update(int i, int delta) {
        while (i < sums.length) {
            sums[i] += delta;
            i += i & -i;
        }
    }

    public int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += sums[i];
            i -= i & -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);
 */

Approach #2 Segment Tree

update time O(logn)

class NumArray {
  SegmentTree segmentTree;

  public NumArray(int[] nums) {
    segmentTree = new SegmentTree(nums);
  }

  public void update(int i, int val) {
    segmentTree.update(i, val);
  }

  public int sumRange(int i, int j) {
    return segmentTree.search(i, j);
  }
}

class SegmentTree {
  public SegmentTreeNode root;
  public SegmentTree(int[] nums) {
    root = build(nums);
  }

  public int search(int start, int end) {
    return searchHelper(root, start, end);
  }

  private int searchHelper(SegmentTreeNode root, int start, int end) {
    if (root == null || start > end)        return 0;

    if (root.start == start && root.end == end)        return root.sum;

    int mid = root.start + (root.end - root.start) / 2;
    int leftSum = searchHelper(root.left, Math.max(root.start, start), Math.min(mid, end));
    int rightSum = searchHelper(root.right, Math.max(start, mid + 1), Math.min(root.end, end));

    return leftSum + rightSum;
  }

  public void update(int index, int val) {
    updateHelper(root, index, val);
  }

  private void updateHelper(SegmentTreeNode root, int index, int val) {
    if (root == null)        return;
    if (root.start == root.end && index == root.start) {
      root.sum = val;
      return;
    }
    int mid = root.start + (root.end - root.start) / 2;
    if (index <= mid) {
      updateHelper(root.left, index, val);
    } else {
      updateHelper(root.right, index, val);
    }
    root.sum = root.left.sum + root.right.sum;
  }

  private SegmentTreeNode build(int[] nums) {
    return buildHelper(0, nums.length - 1, nums);
  }

  private SegmentTreeNode buildHelper(int start, int end, int[] nums) {
    if (start == end)        return new SegmentTreeNode(start, end, nums[start]);

    int mid = start + (end - start) / 2;
    SegmentTreeNode leftChild = buildHelper(start, mid, nums);
    SegmentTreeNode rightChild = buildHelper(mid + 1, end, nums);

    SegmentTreeNode root = new SegmentTreeNode(start, end, leftChild.sum + rightChild.sum);
    root.left = leftChild;
    root.right = rightChild;

    return root;
  }
}

class SegmentTreeNode {
  int sum;
  int start, end;
  SegmentTreeNode left, right;

  public SegmentTreeNode(int start, int end, int sum) {
    this.sum = sum;
    this.start = start;
    this.end = end;
    left = right = null;
  }
}

#3

// Author: Huahua, running time: 24 ms
class SegmentTreeNode {
public:
  SegmentTreeNode(int start, int end, int sum,
                  SegmentTreeNode* left = nullptr,
                  SegmentTreeNode* right = nullptr): 
    start(start),
    end(end),
    sum(sum),
    left(left),
    right(right){}      
  SegmentTreeNode(const SegmentTreeNode&) = delete;
  SegmentTreeNode& operator=(const SegmentTreeNode&) = delete;
  ~SegmentTreeNode() {
    delete left;
    delete right;
    left = right = nullptr;
  }

  int start;
  int end;
  int sum;
  SegmentTreeNode* left;
  SegmentTreeNode* right;
};

class NumArray {
public:
  NumArray(vector<int> nums) {
    nums_.swap(nums);
    if (!nums_.empty())
      root_.reset(buildTree(0, nums_.size() - 1));
  }

  void update(int i, int val) {
    updateTree(root_.get(), i, val);
  }

  int sumRange(int i, int j) {
    return sumRange(root_.get(), i, j);
  }
private:
  vector<int> nums_;
  std::unique_ptr<SegmentTreeNode> root_;

  SegmentTreeNode* buildTree(int start, int end) {  
    if (start == end) {      
      return new SegmentTreeNode(start, end, nums_[start]);
    }
    int mid = start + (end - start) / 2;
    auto left = buildTree(start, mid);
    auto right = buildTree(mid + 1, end);
    auto node = new SegmentTreeNode(start, end, left->sum + right->sum, left, right);    
    return node;
  }

  void updateTree(SegmentTreeNode* root, int i, int val) {
    if (root->start == i && root->end == i) {
      root->sum = val;
      return;
    }
    int mid = root->start + (root->end - root->start) / 2;
    if (i <= mid) {
      updateTree(root->left, i, val);
    } else {      
      updateTree(root->right, i, val);
    }
    root->sum = root->left->sum + root->right->sum;
  }

  int sumRange(SegmentTreeNode* root, int i, int j) {    
    if (i == root->start && j == root->end) {
      return root->sum;
    }
    int mid = root->start + (root->end - root->start) / 2;
    if (j <= mid) {
      return sumRange(root->left, i, j);
    } else if (i > mid) {
      return sumRange(root->right, i, j);
    } else {
      return sumRange(root->left, i, mid) + sumRange(root->right, mid + 1, j);
    }
  }
};