Data Structures - Segment Tree

学习了下一种新的数据结构，segment tree
主要看这篇文章：
http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

看完之后就基本清楚了。
说说他的应用场景。
假设给你一个array，有两个函数，
一个是，
int sum(int i, int j) 给出 index i-j 的sum

void update(int i, int value) 更新index的值为 value

我的做法是：
建立一个新的数组，
sums[i] = sums[0] + sums[1] + ... + sums[i]
那么
sum(i, j) = sums[j] - sums[i - 1];
当然还要考虑一些Corner case

这个时候， sum 函数时间复杂度是就是O(1),空间复杂度是O(n)

update 呢？
我需要把 涉及到 index 的所有 sums 元素都更新下，
范围是 ： [0, index] in sums[]

时间复杂度是 O(n)

如果用segment tree 来做这道题目，
空间复杂度是 O(n)
sum 时间复杂度是 O(log n)
update 时间复杂度是 O(log n)

My code:

public class SegmentTree {
    private int[] nums;
    private int[] st;
    public void initialize(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        int level = (int ) Math.ceil(Math.log(n) / Math.log(2));
        int len = 2 * (int) Math.pow(2, level) + 1;
        st = new int[len];
        buildST(0, 0, nums.length - 1, st, nums);
    }
    public int getSum(int begin, int end) {
        return getSum(0, begin, end, 0, nums.length - 1);
    }
    
    public void update(int index, int value) {
        int diff = value - nums[index];
        nums[index] = value;
        update(0, diff, index, 0, nums.length - 1);
    }
    
    private int getSum(int index, int qs, int qe, int ss, int se) {
        if (qs <= ss && qe >= se) {
            return st[index];
        }
        else if (qs > se || qe < ss) {
            return 0;
        }
        else {
            int mid = ss + (se - ss) / 2;
            return getSum(2 * index + 1, qs, qe, ss, mid) + getSum(2 * index + 2, qs, qe, mid + 1, se);
        }
    }
    
    private void update(int index, int diff, int i, int ss, int se) {
        if (i < ss || i > se) {
            return;
        }
        else if (ss == se) {
            st[index] += diff;
        }
        else {
            st[index] += diff;
            int mid = ss + (se - ss) / 2;
            update(2 * index + 1, diff, i, ss, mid);
            update(2 * index + 2, diff, i, mid + 1, se);
        }
    }
    
    private int buildST(int index, int begin, int end, int[] st, int[] nums) {
        int mid = begin + (end - begin) / 2;
        if (begin == end) {
            st[index] = nums[begin];
        }
        else {
            st[index] = buildST(2 * index + 1, begin, mid, st, nums) + buildST(2 * index + 2, mid + 1, end, st, nums);
        }
        return st[index];
    }
    
    public static void main(String[] args) {
        int[] nums = new int[]{1,3,5,7,9,11};
        SegmentTree test = new SegmentTree();
        test.initialize(nums);
        int ret = test.getSum(2, 3);
        System.out.println(ret);
        test.update(2, 6);
        ret = test.getSum(2, 3);
        System.out.println(ret);
    }
    
}

不得不说，完整写出这个方法还是很麻烦的。
因为首先你需要构建一个segment tree
然后sum然后update
这些都需要 recursion

整个过程还是很麻烦的。
首先，st的长度 len
int level = (int) (Math.ceiling(Math.log(n) / Math.log(2)));
int len = 2 * (int) Math.pow(2, level) - 1;
int[] st = new int[len];

然后就是用一些divide and conquer的思想来完成sum and update

然后是segment tree 的另外一个应用，求
range minimum query

给定一个数组 nums[]
求 [i, j] 间的最小数。
可以遍历，复杂度是O(n)
如果用segment tree,
同样， query: time O(log n)
update: time O(log n)
参考网址：
http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

代码如下:
My code:

public class SegmentTree_RMQ {
    private int[] nums;
    private int[] st;
    public void initialize(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        int level = (int ) Math.ceil(Math.log(n) / Math.log(2));
        int len = 2 * (int) Math.pow(2, level) + 1;
        st = new int[len];
        buildST(0, 0, nums.length - 1, st, nums);
    }
    public int getMin(int begin, int end) {
        return getMin(0, begin, end, 0, nums.length - 1);
    }
    
    public void update(int index, int value) {
        int diff = value - nums[index];
        nums[index] = value;
        update(0, diff, index, 0, nums.length - 1);
    }
    
    private int getMin(int index, int qs, int qe, int ss, int se) {
        if (qs <= ss && qe >= se) {
            return st[index];
        }
        else if (qs > se || qe < ss) {
            return Integer.MAX_VALUE;
        }
        else {
            int mid = ss + (se - ss) / 2;
            return Math.min(getMin(2 * index + 1, qs, qe, ss, mid), getMin(2 * index + 2, qs, qe, mid + 1, se));
        }
    }
    
    private int update(int index, int diff, int i, int ss, int se) {
        if (i < ss || i > se) {
            return 0;
        }
        else if (ss == se) {
            st[index] += diff;
            return st[index];
        }
        else {
            int mid = ss + (se - ss) / 2;
            return Math.min(update(2 * index + 1, diff, i, ss, mid), update(2 * index + 2, diff, i, mid + 1, se));
        }
    }
    
    private int buildST(int index, int begin, int end, int[] st, int[] nums) {
        int mid = begin + (end - begin) / 2;
        if (begin == end) {
            st[index] = nums[begin];
        }
        else {
            st[index] = Math.min(buildST(2 * index + 1, begin, mid, st, nums), buildST(2 * index + 2, mid + 1, end, st, nums));
        }
        return st[index];
    }
    
    public static void main(String[] args) {
        int[] nums = new int[]{1,3,5,7,9,11};
        SegmentTree_RMQ test = new SegmentTree_RMQ();
        test.initialize(nums);
        int ret = test.getMin(2, 3);
        System.out.println(ret);
        test.update(2, 9);
        ret = test.getMin(2, 3);
        System.out.println(ret);
    }
    
}

其实掌握了segment tree思想后，这两道题目都差不多了。
那么，segment tree适用于哪种情形呢？
适用于在array中，给定一个范围，求sum，求最小值，求最大值，等等。
而且，求值操作很多，update操作也很多。这个时候用 segment tree是最理想的。如果update并不多，那完全可以用一些牺牲空间的方法来做。

记得有个类型题目，是什么 range query，应该都可以用segment tree来做。马上都写一下。

暂且总结到这里吧。

Anyway, Good luck, Richardo! -- 09/04/2016