线段树详解分析

什么是线段树？

是用来存放给定区间（segment, or interval）内对应信息的一种数据结构。与树状数组（binary indexed tree）相似，线段树也用来处理数组相应的区间查询（range query）和元素更新（update）操作。与树状数组不同的是，线段树不止可以适用于区间求和的查询，也可以进行区间最大值，区间最小值（Range Minimum/Maximum Query problem）或者区间异或值的查询。

对应于树状数组，线段树进行更新（update）的操作为O(logn)，进行区间查询（range query）的操作也为O(logn)。

线段树是用一个完全二叉树来存储对应于其每一个区间（segment）的数据。该二叉树的每一个结点中保存着相对应于这一个区间的信息。同时，线段树所使用的这个二叉树是用一个数组保存的，与堆（Heap）的实现方式相同。

线段树的作用？

线段树可以使用log(n) 的时间复杂度来进行更新和查询数组范围的和。

构建线段树

线段树在初始化时可以创建4倍原数组大小的空间

static class SegmentTree {

        int[] tree;
        int N = 100;

        public SegmentTree() {
            tree = new int[N];
        }

        public void build_tree(int[] arr, int node, int start, int end) {
            if (start == end) {
                tree[node] = arr[start];
            }else {
                int mid = (start + end) / 2;
                int left_node = node * 2 + 1;
                int right_node = node * 2 + 2;
                build_tree(arr, left_node, start, mid);
                build_tree(arr, right_node, mid + 1, end);
                tree[node] = tree[left_node] + tree[right_node];
            }
        }

        public void update_tree(int[] arr, int node, int start, int end, int idx , int val){
            if (start == end){
                arr[idx] = val;
                tree[node] = val;
                return;
            }
            int mid = (start + end)/2;
            int left_node = node * 2 + 1;
            int right_node = node * 2 + 2;
            if(idx <= mid) {
                update_tree(arr, left_node, start, mid, idx, val);
            }else {
                update_tree(arr,right_node,mid+1,end,idx,val);
            }
            tree[node] = tree[left_node] + tree[right_node];
        }

        public int query_tree(int[] arr, int node, int start, int end,int L, int R){
            if(L > end || R < start){
                return 0;
            }
            else if(L <= start && R >= end){
                return tree[node];
            }
            else if(start == end){
                return tree[node];
            }
            int mid = (start + end)/2;
            int left_node = node * 2 + 1;
            int right_node = node * 2 + 2;
            int left_sum = query_tree(arr,left_node,start,mid,L,R);
            int right_sum = query_tree(arr,right_node,mid+1,end,L,R);
            return left_sum + right_sum;
        }

        public void print(){
            for (int i =0;i<15;i++){
                System.out.println(tree[i]);
            }
        }
    }

eg

307. 区域和检索 - 数组可修改

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。

示例:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

class NumArray {
    
    int[] tree;
    int[] arr;
    public NumArray(int[] nums) {
        tree = new int[nums.length * 4 + 1];
        this.arr = nums;
        if(nums != null && nums.length != 0){
        build_tree(0,0,nums.length-1);
    }
    }

    public void build_tree(int node, int start, int end){
        if(start == end){
            tree[node] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        int left_node = node * 2 + 1;
        int right_node = node * 2 + 2;
        build_tree(left_node,start,mid);
        build_tree(right_node,mid+1,end);
        tree[node] = tree[left_node] + tree[right_node];
    }
    
    public void update(int i, int val) {
        update_tree(0,0,arr.length-1,i,val);
    }

    public void update_tree(int node,int start,int end, int i, int val){
        if(start == end){
            tree[node] = val;
            arr[i] = val;
            return;
        }
        int mid = (start + end)/2;
        int left_node = node * 2 + 1;
        int right_node = node * 2 + 2;
        if(i <= mid){
            update_tree(left_node,start,mid,i,val);
        }else{
            update_tree(right_node,mid+1,end,i,val);
        }
        tree[node] = tree[left_node] + tree[right_node];
    }
    
    public int sumRange(int i, int j) {
        return query_tree(0,0,arr.length-1,i,j);
    }

    public int query_tree(int node, int start, int end, int L, int R){
        if(R < start || L > end){
            return 0;
        }
        else if(L >= start && R <= end){
            return tree[node];
        }else if(start == end){
            return tree[node];
        }
        int mid = (start + end)/2;
        int left_node = node * 2 + 1;
        int right_node = node * 2 + 2;
        int left_sum = query_tree(left_node,start,mid,L,R);
        int right_sum = query_tree(right_node,mid+1,end,L,R);
        return left_sum + right_sum;
    }
}