【数据结构】了解线段树与操作线段树的基本方法

package com.hyc.DataStructure.SegmentTree;

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.SegmentTree
 * @className: SegmentTree
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/26 10:15
 * @version: 1.0
 */
public class SegmentTree {
    @Override
    public String toString() {
        return "SegmentTree{" +
                "start=" + start +
                ", end=" + end +
                ", val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }

    public static void main(String[] args) {
        int[] arr = {1, 4, 2, 3};
        SegmentTree root = SegmentTree.build(arr);
        System.out.println(root);
    }

    //节点区间范围
    public int start, end;
    //    存储节点值
    public int val;
    //    左右子树
    public SegmentTree left;
    public SegmentTree right;

    public SegmentTree(int start, int end, int val) {
        this.start = start;
        this.end = end;
        this.val = val;
    }

    public static SegmentTree build(int[] A) {
        return buildByRecu(0, A.length - 1, A);
    }

    public static SegmentTree buildByRecu(int start, int end, int[] A) {
        if (start > end) {
            return null;
        }
        SegmentTree root = new SegmentTree(start, end, A[start]);
        //    如果是叶子节点 直接返回
        if (start == end) {
            return root;
        }
        //    如果不是那么就以二分的形式来递归创建树
        int mid = (start + end) / 2;
        root.left = buildByRecu(start, mid, A);
        root.right = buildByRecu(mid + 1, end, A);
        //求出区间内最大值为父节点的val
        root.val = Math.max(root.left.val, root.right.val);
        return root;
    }
}

    public static void modify(SegmentTree root, int index, int value) {
        //    先找到叶子节点,然后逐渐上层
        if (root.start == root.end && root.start == index) {
            root.val = value;
            return;
        }

        int mid = (root.start + root.end) / 2;
        //    判断index 在左子树的区间,还是 右子树的区间,二分思路
        if (index <= mid) {
            modify(root.left, index, value);
            root.val = Math.max(root.left.val, root.right.val);
            return;
        }
        modify(root.right, index, value);
        root.val = Math.max(root.left.val, root.right.val);
    }

    public static int searchByIndex(SegmentTree root, int index) {
        //    先找到叶子节点,然后逐渐上层
        if (root.start == root.end && root.start == index) {

            return root.val;
        }

        int mid = (root.start + root.end) / 2;
        //    判断index 在左子树的区间,还是 右子树的区间,二分思路
        if (index <= mid) {
            searchByIndex(root.left, index);

            return root.val;
        }
        searchByIndex(root.right, index);
        return root.val;
    }