小学六年级学生写的 “线段树”解析，厉害了！

作者 | 王乙堃 

来源 | 程序员小灰

线段树是一个复杂的数据结构，比较难理解，也比较难解释清楚。在我将这个数据结构反复学习了五遍的时候，我终于有了信心写出这篇介绍线段树的文章。希望大家能够掌握这种数据结构。

这篇文章比较长，建议大家耐心阅读，好好消化吸收哦~~

前置内容

学习线段树前，你需要掌握二叉搜索树，我只补充一个内容，就是关于二叉搜索树如何编号。

二叉搜索树的根节点编号为1，对于每个节点，假如其编号为N，它的左儿子编号为2N，右儿子编号为2N+1。因此，整个二叉搜索树的编号如下：

上图当中，结点上方的数字是结点的编号，后续为了简单，把编号写在结点内不。

有读者可能要问了，为什么3的儿子是6和7，而不是4和5呢？这是因为虽然节点4和节点5不存在，但是仍然应该为他们保留4和5这2个编号，你可以把这棵树看成这样：

线段树的概念

线段树，英文名称是 Segment Tree，其本质也是一个二叉搜索树，区别在于线段树的每一个节点记录的都是一个区间，每个区间都被平均分为2个子区间，作为它的左右儿子。比如说区间[1，10]，被分为区间[1，5]作为左儿子，区间[6，10]作为右儿子：

为什么要设计这样奇怪的数据结构呢？

线段树主要适用于某些相对罕见的应用场景：

比如给定了若干元素，要求统计出不同区间范围内，元素的个数。

现在我们已经知道了什么是线段树，那么看一个利用线段树的例子。

线段树的存储与建造

这是一个序列：

现在我们要用它完成一个区间求和的任务。

区间求和就是指求序列中一段区间的所有元素之和。比如说上面的序列，区间[1，5]的和为元素1+元素2+元素3+元素4+元素5，也就是14。再举一个例子，区间[9，10]的和为9。

在学习线段树的概念的时候，我们就知道线段树的每个节点都存储了一个区间。比如说对于[1，10]这个节点，也就是这棵线段树的根节点，那么它的值为1+5+1+3+4+2+0+9+0+9=34。看我们把这棵树填完：

（当一个区间的左右边界已经相等时，比如[1，1]，表示这个区间内只有一个元素了，此时不能再分割，因此它就没有左右儿子节点了）

现在就让我们用代码实现线段树：

【代码片段 1】 用一个类Node表示线段树的节点：

class Node {
     int l; // l是区间左边界
     int r; // r是区间右边界
     int sum; // sum是区间元素和

     public Node (int l, int r, int sum){
         this.l = l;
         this.r = r;
         this.sum = sum;
     }
}

【代码解析 1】 线段树的任意节点都有3个属性：

• 区间的左边界l

• 区间的右边界r

• 区间的元素和sum

比如说在上面的线段树中，区间[1,10]这个元素：

• 左边界为1

• 右边界为10

• 元素和为34

【代码片段 2】 定义元素个数、原序列和线段树

static int n = 10; // n是元素个数
static int[] array = {0, 1, 5, 1, 3, 4, 2, 0, 9, 0, 9}; 
// array是原序列(第一个0是占array[0]位的)
static Node[] tree = new Node[4*n];

static void initTree (){
    for(int i = 0; i