学习了下一种新的数据结构，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
