数据结构-Segment Tree 线段树

public class SegmentTree {

private int[] segmentTree;
    private int n;

public SegmentTree(int[] nums) {
        n = nums.length;
        segmentTree = new int[nums.length * 4];//一般需要4倍数组大小
        build(0, 0, n - 1, nums);//构建线段树
    }
    //[1, 2, 3, 4, 5]
    //[15, 6, 9, 3, 3, 4, 5, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    private void build(int node, int s, int e, int[] nums) {
        if (s == e) {// 如果 start==end 那递归结束，当前区间只有一个数(节点),segmentTree[node] = nums[s]
            segmentTree[node] = nums[s];
            return;
        }
        int m = s + (e - s) / 2;//取中点（防止溢出）
        build(node * 2 + 1, s, m, nums);//构建左子树
        build(node * 2 + 2, m + 1, e, nums);//构建右子树
        segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2];//当前数节点
    }
}

public void update(int index, int val) {
    change(index, val, 0, 0, n - 1);
}
private void change(int index, int val, int node, int s, int e) {
    if (s == e) {//递归结束（查找到对应的下标）
        segmentTree[node] = val;//更新最新值
        return;
    }
    int m = s + (e - s) / 2;//获取中点
    if (index <= m) {//如果m>=index说明在左边区间
        change(index, val, node * 2 + 1, s, m);
    } else {//否则在右边区间
        change(index, val, node * 2 + 2, m + 1, e);
    }
    //更新父节点
    segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2];
}

public int sumRange(int left, int right) {
    return range(left, right, 0, 0, n - 1);
}

/**
 * 范围求和 range 函数
 * 给定区间 [left,right] 时，我们将区间 [left,right] 拆成多个结点对应的区间。
 * 如果结点 node 对应的区间与 [left,right] 相同，可以直接返回该结点的值，即当前区间和。
 * 如果结点 node 对应的区间与 [left,right] 不同，设左子结点对应的区间的右端点为 m，那么将区间 [left,right] 沿点 m 拆成两个区间，分别计算左子结点和右子结点。
 * 我们从根结点开始递归地拆分区间 [left,right]
 *
 * @param left 目标范围左索引
 * @param right 目标范围右索引
 * @param node 当前索引
 * @param s 开始左区间
 * @param e 结束右区间
 * @return 返回[left,right]数值之和
 */
private int range(int left, int right, int node, int s, int e) {
    //（递归结束）没有重叠范围，返回当前节点
    if (left == s && right == e) return segmentTree[node];
    int m = s + (e - s) / 2;//获取中点
    if (right <= m) {//如果right <= m说明[left,right]在全部左区间
        return range(left, right, node * 2 + 1, s, m);
    } else if (left > m) {//如果right <= m说明[left,right]在全部在右区间
        return range(left, right, node * 2 + 2, m + 1, e);
    } else {//否则[left,right]有部分在左区间有部分在右区间，把两者相加即可
        return range(left, m, node * 2 + 1, s, m) + range(m + 1, right, node * 2 + 2, m + 1, e);
    }
}

class NumArray {
    //线段数（叶子节点都是数组的元素）
    //[1,3,5]       [1,3,5,7]        ......
    //      9           16
    //     / \         /  \
    //    4   5       4    12
    //   / \         / \   / \
    //  1   3       1   3 5   7      ......
    // n=3 node=6   n=4 node=7     n=5 node=9  n=6 node=12  node<=2*n
    int[] tree;
    int n;
    public NumArray(int[] nums) {
        n = nums.length;
        tree = new int[2*n];
        buildTree(nums);
    }
    //构建线段树
    public void buildTree(int[] nums){
        //nums=[1,3,5,7] tree = [0,0,0,0,1,3,5,7]
        //将所有叶子节点放置在[n,2n)数组中
        for (int i = n, j = 0;  i < 2 * n; i++,  j++)tree[i] = nums[j];
        //tree = [0,16,4,12,1,3,5,7]
        //把父节点放置在[1,n)数组中 , tree[i] = tree[i * 2] + tree[i * 2 + 1]
        for (int i = n - 1; i > 0; --i)tree[i] = tree[i * 2] + tree[i * 2 + 1];
    }
    //更新某个下标同时需要更新其父节点的值
    public void update(int index, int val) {
        index+=n;//下标的位置,n+下标
        tree[index] = val;
        //更新父亲节点,因为tree[i] = tree[i * 2] + tree[i * 2 + 1];所以index如果是奇数则为右子树，index是偶数则为左子树
        while(index>0){
            int left = index;
            int right = index;
            if(index % 2 == 0) right = index+1;
            else left = index - 1;
            //更新父节点值
            tree[index / 2] = tree[left] + tree[right];
            //更新下标
            index /= 2;
        }

}
    //求和只需要获取其父节点
    public int sumRange(int left, int right) {//left，right为下标
        //确认在数组中的下标
        left+=n;
        right+=n;
        int ret = 0;
        //[1,3,5,7]
        while(left<=right){
            //1.如果left是左子树可以直接取根节点,如果是右子树那只取右节点
            if(left % 2 == 1 ){
                ret+=tree[left];
                left++;
            }
            //2.如果right是右子树可以直接取根节点,如果是左子树那只取左节点
            if(right % 2 == 0 ){
                ret+=tree[right];
                right--;
            }
            left/=2;
            right/=2;
        }
        return ret;
    }
}

package io.example.algorithm.tree;

//线段数（叶子节点都是数组的元素）
//   [1,3,5]    [1,3,5,7]        ......
//      9           16
//     / \         /  \
//    4   5       4    12
//   / \         / \   / \
//  1   3       1   3 5   7      ......
// n=3 node=5   n=4 node=7   n=5 node=9  n=6 node=12  node<=2*n
public class SegmentTree {

// 设置数组的最大值
    int N = 100000;
    int n; //节点个数
    // 设置数组的最大值
    int[] tree = new int[2 * N];

//                                           |--------|
    //                                           |       +-+
    // 构建线段树                                  v       | |
    //[1,3,5,7] -> [0,0,0,0][1,3,5,7] -> [0,16,4,12][1,3,5,7]
    //                                         ^     | |
    //                                         |     +-+
    //                                         |------|
    void buildTree(int[] arr) {
        // [n,2n)按照顺序存储节点
        for (int i = 0; i < n; i++) tree[n + i] = arr[i];
        // 构建父节点(0,n) 父节点等于 tree[i] = tree[i * 2] + tree[i * 2 + 1];
        for (int i = n - 1; i > 0; --i) tree[i] = tree[i << 1] + tree[i << 1 | 1];
    }

/**
     * 更新树节点
     * @param p 下标
     * @param value 值
     */
    void updateTreeNode(int p, int value) {
        // 直接更新值
        tree[p + n] = value;
        p = p + n;
        // 同时需要更新其父亲节点
        for (int i = p; i > 1; i = i / 2) tree[i / 2] = tree[i] + tree[i ^ 1];
        for (int i = p; i > 1; i >>= 1) tree[i >> 1] = tree[i] + tree[i ^ 1];
    }

// function to get sum on
    // interval [l, r)
    int query(int l, int r) {
        int res = 0;
        // loop to find the sum in the range
        // for (l += n, r += n; l < r; l = l / 2, r = r / 2) {
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if ((l & 1) > 0) res += tree[l++];
            if ((r & 1) > 0) res += tree[--r];
        }
        return res;
    }

public static void main(String[] args) {
        SegmentTree segmentTree = new SegmentTree();
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        // n is global
        segmentTree.n = a.length;
        // 构建数
        segmentTree.buildTree(a);
        // print the sum in range(1,2)
        // index-based
        System.out.println(segmentTree.query(1, 3));
        // modify element at 2nd index
        segmentTree.updateTreeNode(2, 1);
        // print the sum in range(1,2)
        // index-based
        System.out.println(segmentTree.query(1, 3));
    }
}