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]

  1. sumRange(0, 2) -> 9
  2. update(1, 2)
  3. 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.

    分析

由于需要求任意段的和，且会随机修改元素，用线段树(Segment Tree)再合适不过了。

另外一个数据结构，树状数组(Binary Indexed Tree)，也适合解这道题。

解法1 线段树

  1. // Range Sum Query - Mutable
  2. // Segment Tree
  3. public class NumArray {
  4.     private SegmentTreeNode root;
  6.     // Time Complexity: O(n)
  7.     public NumArray(int[] nums) {
  8.         this.root = buildTree(nums, 0, nums.length);
  9.     }
  11.     // Time Complexity: O(log n)
  12.     void update(int i, int val) {
  13.         updateHelper(this.root, i, val);
  14.     }
  16.     // Time Complexity: O(log n)
  17.     public int sumRange(int i, int j) {
  18.         return sumRangeHelper(this.root, i, j+1);
  19.     }
  21.     private static SegmentTreeNode buildTree(int[] nums, int begin, int end) {
  22.         if (nums == null || nums.length == 0 || begin >= end)
  23.             return null;
  24.         if (begin == end - 1) // one element
  25.             return new SegmentTreeNode(begin, end, nums[begin]);
  27.         final SegmentTreeNode root = new SegmentTreeNode(begin, end);
  28.         final int middle = begin + (end - begin) / 2;
  29.         root.left = buildTree(nums, begin, middle);
  30.         root.right = buildTree(nums, middle, end);
  31.         root.sum = root.left.sum + root.right.sum;
  33.         return root;
  34.     }
  36.     private static void updateHelper(SegmentTreeNode root, int i, int val) {
  37.         if (root.begin == root.end - 1 && root.begin == i) {
  38.             root.sum = val;
  39.             return;
  40.         }
  42.         final int middle = root.begin + (root.end - root.begin) / 2;
  43.         if (i < middle) {
  44.             updateHelper(root.left, i, val);
  45.         } else {
  46.             updateHelper(root.right, i, val);
  47.         }
  49.         root.sum = root.left.sum + root.right.sum;
  50.     }
  51.     private static int sumRangeHelper(SegmentTreeNode root, int begin, int end) {
  52.         if (root == null || begin >=root.end || end <= root.begin)
  53.             return 0;
  54.         if (begin <= root.begin && end >= root.end)
  55.             return root.sum;
  57.         final int middle = root.begin + (root.end - root.begin) / 2;
  58.         return sumRangeHelper(root.left, begin, Math.min(end, middle)) +
  59.                 sumRangeHelper(root.right, Math.max(middle, begin), end);
  60.     }
  62.     static class SegmentTreeNode {
  63.         private int begin;
  64.         private int end;
  65.         private int sum;
  66.         private SegmentTreeNode left;
  67.         private SegmentTreeNode right;
  69.         public SegmentTreeNode(int begin, int end, int sum) {
  70.             this.begin = begin;
  71.             this.end = end;
  72.             this.sum = sum;
  73.         }
  74.         public SegmentTreeNode(int begin, int end) {
  75.             this(begin, end, 0);
  76.         }
  77.     }
  78. }

解法2 树状数组

  1. // Range Sum Query - Mutable
  2. // Binary Indexed Tree
  3. public class NumArray {
  4.     private int[] nums;
  5.     private int[] bit;
  7.     // Time Complexity: O(n)
  8.     public NumArray(int[] nums) {
  9.         // index 0 is unused
  10.         this.nums = new int[nums.length + 1];
  11.         this.bit = new int[nums.length + 1];
  13.         for (int i = 0; i < nums.length; ++i) {
  14.             update(i, nums[i]);
  15.         }
  16.     }
  18.     // Time Complexity: O(log n)
  19.     public void update(int index, int val) {
  20.         final int diff = val - nums[index + 1];
  21.         for (int i = index + 1; i < nums.length; i += lowbit(i)) {
  22.             bit[i] += diff;
  23.         }
  24.         nums[index + 1] = val;
  25.     }
  27.     // Time Complexity: O(log n)
  28.     public int sumRange(int i, int j) {
  29.         return read(j + 1) - read(i);
  30.     }
  32.     private int read(int index) {
  33.         int result = 0;
  34.         for (int i = index; i > 0; i -= lowbit(i)) {
  35.             result += bit[i];
  36.         }
  37.         return result;
  38.     }
  40.     private static int lowbit(int x) {
  41.         return x & (-x);  // must use parentheses
  42.     }
  43. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/binary-tree/segment-tree/range-sum-query-mutable.html