php开发手册线段树是为区间更新和区间查询而生的数据结构，旨在快速解决区间问题力软开发框架的开发手册

2022-03-25

线段树是一种用于区间更新和区间查询的数据结构，旨在快速解决区间问题。

一般来说，线段树不会添加节点，也不支持动态添加节点。段树也是二叉树的一种，但它的节点是由一个区间定义的。叶节点是具有单个间隔的节点。所以线段树本质上是一棵区间树。

我们在搜索的时候，只需要找出哪些子区间构成了结果区间。

实现代码

先定义基本结构

public class SegmentTree {
    
    private Integer value;
    private Integer maxValue;
    private Integer l;
    private Integer r;
    
    private SegmentTree leftChild;
    private SegmentTree rightChild;
}
复制代码

l 和 r 用于唯一地表征这个区间。那么其他的内容就和标准的二叉树没什么区别了。

建树过程

和二叉树构造没什么区别，我们这里使用的是前序构造方法。代码显示如下：

public static SegmentTree buildTree(int left, int right, int[] value) {
    if (left > right) {
        return null;
    }
    SegmentTree node = new SegmentTree();
    node.setValue(value[left]);
    node.setL(left);
    node.setR(right);
    if (left == right) {
        // TODO: 2022/1/17 退出条件
        node.setMaxValue(node.getValue());
        return node;
    }
    int mid = (left + right) >>> 1;
    node.setLeftChild(buildTree(left, mid, value));
    node.setRightChild(buildTree(mid + 1, right, value));
    if (Objects.isNull(node.getLeftChild())) {
        if (Objects.isNull(node.getRightChild())) {
            node.setMaxValue(node.getValue());
        } else {
            node.setMaxValue(node.getRightChild().getMaxValue());
        }
    } else {
        if (Objects.isNull(node.getRightChild())) {
            node.setMaxValue(node.getLeftChild().getMaxValue());
        } else {
            node.setMaxValue(Math.max(node.getLeftChild().getMaxValue(),
                                      node.getRightChild().getMaxValue()));
        }
    }
    return node;
}
复制代码

可以看出，这里叶子节点的判断条件是 left == 。在其他方面，它与二叉树没有什么不同。

查询区间最大值

public static Integer getMaxValue(SegmentTree segmentTree, int left, int right) {
    if (Objects.isNull(segmentTree)) return null;
    if (segmentTree.getL() == left && segmentTree.getR() == right) {
        System.out.println("获取了区间 [" + left + "," + right + "] 的最大值" + segmentTree.getMaxValue());
        return segmentTree.getMaxValue();
    }
    int segMid = (segmentTree.getL() + segmentTree.getR()) >>> 1;
    if (segMid < left) {
        return getMaxValue(segmentTree.getRightChild(), left, right);
    }
    if (segMid >= right) {
        return getMaxValue(segmentTree.getLeftChild(), left, right);
    }
    // TODO: 2022/1/17 左半边答案
    Integer leftMax = getMaxValue(segmentTree.getLeftChild(), left, segMid);
    Integer rightMax = getMaxValue(segmentTree.getRightChild(), segMid + 1, right);
    if (Objects.isNull(leftMax)) {
        if (Objects.isNull(rightMax)) {
            return -100000;
        } else {
            return rightMax;
        }
    } else {
        if (Objects.isNull(rightMax)) {
            return leftMax;
        } else {
            return Math.max(leftMax, rightMax);
        }
    }
}
复制代码

从上面的代码分析，设置当前节点的区间为[L,R]，那么对于区间[l,r]的最大值，需要进行分类讨论。如果LR区间的中点Mid在lr区间的左侧，则max(lr) = max( , l, r); 如果LR区间的中点在lr区间的右侧，则max(lr) = max(left , l, r); 如果 Mid 在 lr 区间内，max(lr) = max(left , l, mid) 和 max( , mid+1, r) 中的较大者。

我们来看看测试用例和运行结果：

public static void main(String[] args) {
    int[] a = new int[]{2, 5, 4, 7, 6, 0, 1, -1, 2, 3, 6, 7, 0, 2, 9, 8, 5, 4, 7, 2};
    SegmentTree segmentTree = buildTree(0, a.length - 1, a);
    System.out.println(getMaxValue(segmentTree, 0, 16));
}
复制代码

结果如下

得到区间[0,9]的最大值 7 得到区间[10,14]的最大值得到区间[15,16]的最大值 8 9

得到间隔和

现在需要改变原来的建树过程。首先php开发手册，将 sum 字段添加到基础架构

public class SegmentTree {
    private Integer value;
    private Integer maxValue;
    private Integer sum;
    private Integer l;
    private Integer r;
    private SegmentTree leftChild;
    private SegmentTree rightChild;
}
复制代码

然后在构造方法中，加上sum的维护

public static SegmentTree buildTree(int left, int right, int[] value) {
    if (left > right) {
        return null;
    }
    SegmentTree node = new SegmentTree();
    node.setValue(value[left]);
    node.setL(left);
    node.setR(right);
    if (left == right) {
        // TODO: 2022/1/17 退出条件
        node.setMaxValue(node.getValue());
        node.setSum(node.getValue());
        return node;
    }
    int mid = (left + right) >>> 1;
    node.setLeftChild(buildTree(left, mid, value));
    node.setRightChild(buildTree(mid + 1, right, value));
    if (Objects.isNull(node.getLeftChild())) {
        if (Objects.isNull(node.getRightChild())) {
            node.setMaxValue(node.getValue());
            node.setSum(node.getValue());
        } else {
            node.setMaxValue(node.getRightChild().getMaxValue());
            node.setSum(node.getRightChild().getSum());
        }
    } else {
        if (Objects.isNull(node.getRightChild())) {
            node.setMaxValue(node.getLeftChild().getMaxValue());
            node.setSum(node.getLeftChild().getSum());
        } else {
            node.setMaxValue(Math.max(node.getLeftChild().getMaxValue(),
                                      node.getRightChild().getMaxValue()));
            node.setSum(node.getLeftChild().getSum() + node.getRightChild().getSum());
        }
    }
    return node;
}
复制代码

然后得到总和

public static Integer getSum(SegmentTree segmentTree, int left, int right) {
    if (Objects.isNull(segmentTree)) return null;
    if (segmentTree.getL() == left && segmentTree.getR() == right) {
        System.out.println("获取了区间 [" + left + "," + right + "] 的和" + segmentTree.getSum());
        return segmentTree.getSum();
    }
    int segMid = (segmentTree.getL() + segmentTree.getR()) >>> 1;
    if (segMid < left) {
        return getSum(segmentTree.getRightChild(), left, right);
    }
    if (segMid >= right) {
        return getSum(segmentTree.getLeftChild(), left, right);
    }
    // TODO: 2022/1/17 左半边答案
    Integer leftSum = getSum(segmentTree.getLeftChild(), left, segMid);
    Integer rightSum = getSum(segmentTree.getRightChild(), segMid + 1, right);
    if (Objects.isNull(leftSum)) {
        if (Objects.isNull(rightSum)) {
            return segmentTree.getSum();
        } else {
            return rightSum;
        }
    } else {
        if (Objects.isNull(rightSum)) {
            return leftSum;
        } else {
            return leftSum + rightSum;
        }
    }
}
复制代码

测试过程和结果如下：

public static void main(String[] args) {
    int[] a = new int[]{2, 5, 4, 7, 6, 0, 1, -1, 2, 3, 6, 7, 0, 2, 9, 8, 5, 4, 7, 2};
    SegmentTree segmentTree = buildTree(0, a.length - 1, a);
    System.out.println(getSum(segmentTree,0,3));
}
复制代码

得到区间[0,2]之和 11 得到区间[3,3]之和 7 18

单点更新

/**
     * 这里的left == right
     *
     * @param segmentTree
     * @param left
     * @param right
     * @param value
     */
public static void update(SegmentTree segmentTree, int left, int right, int value) {
    if (segmentTree.getL() == left && segmentTree.getR() == right) {
        segmentTree.setValue(value);
        segmentTree.setMaxValue(value);
        segmentTree.setSum(value);
        return;
    }
    int mid = (segmentTree.getL() + segmentTree.getR()) >>> 1;
    if (mid >= left) {
        update(segmentTree.getLeftChild(), left, right, value);
    }
    if (mid < left) {
        update(segmentTree.getRightChild(), left, right, value);
    }
    segmentTree.setMaxValue(Math.max(segmentTree.getLeftChild().getMaxValue(),segmentTree.getRightChild().getMaxValue()));
    segmentTree.setSum(segmentTree.getLeftChild().getSum() + segmentTree.getRightChild().getSum());
}
复制代码

更新时采用递归的方式从左右节点不断寻找需要更新的区间，同时更新上级节点的最新值。

总结

您可以根据需要扩展它。请记住小程序开发，线段树是以区间为维度的二叉树，或以二维维度为特征的二叉树。普通的二叉树只有一维。这样php开发手册，我们在计算多维值的时候网站优化，其实可以这样构造线段树（二维树、三维树、n维树）。不管树的维数多少，找到结束状态和子状态是关键中的关键。典型的方法是分类讨论。前期不要怕分太多，太细可以合并。

最后

如果你觉得这篇文章对你有一点帮助，请给它一个大拇指。或者你也可以加入我的开发交流群：互相学习，我们会有专业的技术答疑

如果你觉得这篇文章对你有用，请给我们的开源项目一个小星星：非常感谢！

PHP学习手册：

技术交流论坛：