Segment Tree 的应用

最适合用 Segment tree 的情形最好同时满足以下三点：

• 区间查找 min/max

• 频繁 update

• 频繁 query

Range Sum Query - Mutable

非常不错的一道题，Segment Tree的常用操作都考到了。

这题更快的做法是用 Binary Indexed Tree。

但是这道题不用BIT便可以run所有的testcase。后面的题有的就不行了。

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

         SegmentTreeNode root;

         public NumArray(int[] nums) {
             root = buildTree(0, nums.length - 1, nums);
         }

         private SegmentTreeNode buildTree(int start, int end, int[] nums) {
             if (nums == null || start > end) {
                 return null;
             }
             if (start == end) {
                 return new SegmentTreeNode(start, end, nums[start]);
             }

             int mid = start + (end - start) / 2;

             SegmentTreeNode left = buildTree(start, mid, nums);
             SegmentTreeNode right = buildTree(mid + 1, end, nums);
             SegmentTreeNode root = new SegmentTreeNode(start, end, left.sum + right.sum);
             root.left = left;
             root.right = right;
             return root;
         }

         void update(int i, int val) {
             update(root, i, val);
         }

         private void update(SegmentTreeNode root, int index, int value) {
             if (root == null || index < root.start || index > root.end) {
                 return;
             }
             if (index == root.start && index == root.end) {
                 root.sum = value;
                 return;
             }
             update(root.left, index, value);
             update(root.right, index, value);
             root.sum = root.left.sum + root.right.sum;
         }

         public int sumRange(int i, int j) {
             return sumRange(root, i, j);
         }

         private int sumRange(SegmentTreeNode root, int start, int end) {
             if (root == null || start > end || start > root.end || end < root.start) {
                 return 0;
             }
             start = Math.max(start, root.start);
             end = Math.min(end, root.end);
             if (start == root.start && end == root.end) {
                 return root.sum;
             }
             int left = sumRange(root.left, start, end);
             int right = sumRange(root.right, start, end);
             return left + right;
         }
     }
}

Range Sum Query - Immutable

这题从类型上讲，看着和上一题非常像。然而其实这题因为需要的操作比较简单，其实就是一个 prefix sum 数组的 dp ...

教育了我们 segment tree 虽屌，也不要一言不合就随便用。。

• 最适合用 Segment tree 的情形最好同时满足以下三点：

  • 区间查找 min/max

  • 频繁 update

  • 频繁 query

• 在只有区间没有 update 的情况下，其实是一个一维/二维的 DP 问题，并不能体现出 segment tree 的优势。

• 前缀和数组记得在最前面加上 sum = 0 的 padding.

public class NumArray {
     int[] prefix;
     public NumArray(int[] nums) {
         if (nums == null || nums.length == 0) {
             return;
         }
         prefix = new int[nums.length + 1];
         prefix[0] = 0;
         prefix[1] = nums[0];
         for (int i = 1; i < nums.length; ++i) {
             prefix[i + 1] = prefix[i] + nums[i];
         }
     }
     public int sumRange(int i, int j) {
         return prefix[j + 1] - prefix[i];
     }
}

Range Sum Query 2D - Mutable

这道题当然可以把矩阵降维之后用 segment tree 解，把一个 region 拆分成若干个 interval of rows 然后把结果加起来，但是很慢。

这题既体现了 segment tree的应用，又暴露了 segment tree的问题。

• width = m, height = n, 现有 1D segment tree 的复杂度

  • build O(mn)

  • update O(log(mn))

  • query O(x * log (mn)) (x为所求矩形内的数的数量)

这题更适合用 binary index tree 解，segment tree的解法不贴了，因为在leetcode上面跑会超时。