Segment Tree 的应用

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

  • 区间查找 min/max

  • 频繁 update

  • 频繁 query

Range Sum Query - Mutable

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

这题更快的做法是用 Binary Indexed Tree，有空我研究下。

public class NumArray {
    private class SegmentTreeNode{
        int start;
        int end;
        int 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(nums, 0, nums.length - 1);
    }

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

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

        SegmentTreeNode left = buildTree(nums, start, mid);
        SegmentTreeNode right = buildTree(nums, mid + 1, end);

        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 i, int val){
        if(root == null) return;
        if(i < root.start) return;
        if(i > root.end) return;

        if(root.start == i && root.end == i) {
            root.sum = val;
            return;
        }

        update(root.left, i, val);
        update(root.right, i, val);

        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 i, int j){
        if(root == null) return 0;
        if(i > root.end) return 0;
        if(j < root.start) return 0;

        i = Math.max(i, root.start);
        j = Math.min(j, root.end);

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

        int left = sumRange(root.left, i, j);
        int right = sumRange(root.right, i, j);

        return left + right;
    }
}


// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);

Range Sum Query - Immutable

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

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

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

  • 区间查找

  • 频繁 update

  • 频繁 query

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

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

public class NumArray {
    int[] prefixSum;

    public NumArray(int[] nums) {
        if(nums == null || nums.length == 0) return;

        prefixSum = new int[nums.length + 1];
        prefixSum[0] = 0;
        prefixSum[1] = nums[0];
        for(int i = 1; i < nums.length; i++){
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
    }

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


// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);

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(n * log (mn))

• 因为这题更适合用 binary index tree 解，另一个教程贴在这里，还有这里，加上这个陈老师推荐的中文帖子

Fenwick tree can also be used to update and query subarrays in multidimensional arrays with complexity , where d is number of dimensions and n is the number of elements along each dimension.

public class NumMatrix {

    private class SegmentTreeNode{
        int start;
        int end;
        int sum;
        SegmentTreeNode left;
        SegmentTreeNode 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;
        }
    }

    int width;
    int height;
    SegmentTreeNode root;

    private int getIndex(int x, int y){
        return x * width + y;
    }

    public NumMatrix(int[][] matrix) {
        if(matrix == null || matrix.length == 0) return;

        height = matrix.length;
        width = matrix[0].length;

        root = buildTree(matrix, 0, width * height - 1);
    }

    private SegmentTreeNode buildTree(int[][] matrix, int start, int end){
        if(start == end) return new SegmentTreeNode(start, end, matrix[start / width][start % width]);

        int mid = start + (end - start) / 2;
        SegmentTreeNode left = buildTree(matrix, start, mid);
        SegmentTreeNode right = buildTree(matrix, mid + 1, end);
        SegmentTreeNode root = new SegmentTreeNode(start, end, left.sum + right.sum);
        root.left = left;
        root.right = right;

        return root;
    }

    public void update(int row, int col, int val) {
        int index = getIndex(row, col);
        update(root, index, val);
    }

    private void update(SegmentTreeNode root, int index, int val){
        if(root == null) return ;
        if(index < root.start) return;
        if(index > root.end) return;

        if(root.start == index && root.end == index){
            root.sum = val;
            return;
        }

        update(root.left, index, val);
        update(root.right, index, val);

        root.sum = root.left.sum + root.right.sum;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        if(col1 == 0 && col2 == width - 1){
            sum = querySum(root, getIndex(row1, col1), getIndex(row2, col2));
        } else {
            for(; row1 <= row2; row1++){
                sum += querySum(root, getIndex(row1, col1), getIndex(row1, col2));
            }
        }


        return sum;
    }

    private int querySum(SegmentTreeNode root, int start, int end){
        if(root == null) return 0;
        if(start > root.end) return 0;
        if(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 = querySum(root.left, start, end);
        int right = querySum(root.right, start, end);

        return left + right;
    }
}


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix = new NumMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.update(1, 1, 10);
// numMatrix.sumRegion(1, 2, 3, 4);