昨天画了个把小时把lintcode上跟线段树的几道题用java做了一下。把线段树相关的几题都Accepted了。。。这里记录一下。
以区间求和 http://www.lintcode.com/zh-cn/problem/interval-sum/ 这题为例，简要讲解下，首先是build方法， 根据一个数组， 构建一个线段树。
class SegmentTreeNode{
public int start, end;
public SegmentTreeNode left, right;
public Long value;
public SegmentTreeNode(int start, int end){
this.start = start;
this.end = end;
this.left = null;
this.right = null;
this.value = 0L;
}
}
首先定义一个树节点，左右子树都是空。
接着是线段树的build方法。
public SegmentTreeNode build(int start, int end){
if (start > end){
return null;
}
if (start == end){
return new SegmentTreeNode(start, end);
}
int middle = start + (end - start) / 2;
SegmentTreeNode root = new SegmentTreeNode(start, end);
SegmentTreeNode left = this.build(start, middle);
SegmentTreeNode right = this.build(middle + 1, end);
root.left = left;
root.right = right;
return root;
}
递归构建整个树， 时间和空间复杂度是多少呢？ 首先看有多少个子节点， 假设数组规模为N，［1～N］，左右子树为［1～N/2］，［N/2＋ 1， N］， 依次递归到最底层， 一共有2N个节点， 在build的过程中没有重复操作， 所以时间复杂度O(N), 空间复杂度也是O(N)。
接着是update操作，
public void update_sum(SegmentTreeNode root, int index, Long value){
if (index == root.start && index == root.end){
root.value = value;
return;
}
int middle = root.start + (root.end - root.start) / 2;
if (index <= middle){
// need to update left segment tree
this.update_sum(root.left, index, value);
}else{
this.update_sum(root.right, index, value);
}
root.value = root.left.value+ root.right.value;
}
对于每个值的update，需要的时间是lgN, 所以时间复杂度为O(NlgN).
接着是query, 也是递归的做法。
public Long query(SegmentTreeNode root, int left, int right){
if(root == null){
return 0L;
}
if (root.start == left && root.end == right){
return root.value;
}
Long left_query = 0L;
Long right_query = 0L;
int middle = root.start + (root.end - root.start) / 2;
if (left <= middle){
// left tree
if (right <= middle){
left_query = this.query(root.left, left,right);
}else{
left_query = this.query(root.left, left, middle);
}
}
if (middle < right){
// right tree
if (left > middle){
right_query = this.query(root.right, left, right);
}else{
right_query = this.query(root.right, middle+1, right);
}
}
return left_query+ right_query;
}
对于每次query, 规模为N的数组， 常数时间内的操作就可以一半的问题规模，二分法，如果一共有M次查询， 时间复杂度为O(MlgN)
绕了一大圈，终于到了正题了，做的这么一堆东西， 线段树什么什么的， 为的就是query的时候，减小相应的时间复杂度,最笨的方法是O(MN)的复杂度。
当然，如果查询的规模不多的话， 构建这个线段树就多此一举了。
所有的东西都有了， 其他的就是怎么完成这道问题了。
public ArrayList<Long> intervalSum(int[] A,
ArrayList<Interval> queries) {
// write your code here
ArrayList<Long> res = new ArrayList<>();
SegmentTreeNode root = this.build(0, A.length - 1);
for(int i= 0; i<A.length; i++){
this.update_sum(root, i, (long)A[i]);
}
//System.out.println(" "+root.left.value+" "+root.right.value);
for(Interval t:queries){
res.add(this.query(root, t.start, t.end));
}
return res;
}
活动下脑筋。。。。
