线段树

昨天画了个把小时把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;
    }

活动下脑筋。。。。