算法细节系列（28）：线段树

大家好，欢迎来到IT知识分享网。

算法细节系列（28）：线段树

详细代码可以fork下Github上leetcode项目，不定期更新。

题目摘自leetcode：

• Leetcode 307. Range Sum Query – Mutable

Leetcode 307. Range Sum Query – Mutable

解法1

这题的特色在于不断更新的nums[i]，所以我们在用累加和进行求解时，每当update一次，都需要更新sums一次，虽然sumRange的复杂度为$O(1)$，但更新的复杂度为$O(n)$。

代码如下：

public class NumArray { 
    int[] nums; public NumArray(int[] nums) { this.nums = nums; sum(); } public void update(int i, int val) { nums[i] = val; sum(); } int[] sums; private void sum(){ sums = new int[nums.length + 1]; for (int j = 0; j < nums.length; ++j){ sums[j+1] = sums[j] + nums[j]; } } public int sumRange(int i, int j) { return sums[j+1] - sums[i]; } }

解法2

想更新就直接更新nums[i]，在sumRange操作时，直接累加i到j的所有元素，所以更新的时间复杂度为$O(1)$，而求和的时间复杂度为$O(n)$。

代码很简单，不写了。

总结：

• 方法1：更新O(n)，求和O(1)
• 方法2：更新O(1)，求和O(n)

有没有折中的办法？有，采用高级数据结构，于是就有了线段树。但线段树为何可以快速解决这个问题？它是怎么来的？

我们来分析下方法1，方法1做了一步很大的改进，记忆化（sums）。如果没有频繁的update操作，这种累加和区间统计效率是最高的，update更新导致sums结构的连锁反应如下图：

如果运气不好，更新index为0的元素，那么sums最坏要更新n-1次，所以平均下来sums的更新复杂度为$O(n)$，当然这是均摊下来的。

究其原因在于累加和区间之间的关系太过强烈，一些简单的想法。

• 不要让区间之间的关系太强烈，那么就让区间与区间尽量独立。

再看方法2，区间之间的关系太独立了，每个元素代表一个点，以至于我们在sumRange时，需要把所有在范围(i,j)的区间加进来。

此时有了另外一个想法：

• 分别以两个点表示一个区间，这样更新两个点的任何一个，都不会影响任何其他区间。

好想法，那如何求任何范围内的sum(i,j)呢？再用单个点表示一个区间呗。

如：

nums = [1,2,3,4]

可以表示成：

我们用index来表示每个结点，也就是区间。这样一来，更新变得独立了，更新点1时，只会影响它的父结点，而周围的兄弟结点不会受到任何影响，更新相比较于方法1要独立的多。

所以更新的操作从原来的$O(1)$变成了$O(\log n)$，再来看看sum求和操作，这种情况求和是关键。

给定求和范围(i,j)，运气最好，直接求(1,4)的和，直接返回，但运气最差，一定会沉降到树底，但由于它是分治方法，树的深度最大也是$\log n$，所以求和最多也是$O(\log n)$。

此时，这种以区间来表示sums(i,j)很好的平衡了更新和求和操作，虽然损失了更新时间复杂度，但整体的更新求和复杂度下降了。

总结：

• 可能对线段树的理解还比较低级，但这种从点【相对独立】的扩展成区间，给我们一个很好的优化思路。
• 其次，如果从空间换时间的角度来看，可以简单认为记录区间的结点数增多了，必然时间复杂度能够有办法下去。

好了，可以看看具体代码了。

public class NumArray { 
    class SegmentTreeNode{ int start, end; SegmentTreeNode left, right; int sum; public SegmentTreeNode(int start, int end) { this.start = start; this.end = end; sum = 0; } @Override public String toString() { return "SegmentTreeNode [start=" + start + ", end=" + end + "]"; } } SegmentTreeNode root = null; private SegmentTreeNode build(int[] nums, int start, int end){ if (end < start) return null; SegmentTreeNode ret = new SegmentTreeNode(start, end); if (start == end) ret.sum = nums[start]; else{ int mid = start + (end - start) / 2; ret.left = build(nums, start, mid); ret.right = build(nums, mid + 1, end); ret.sum = ret.left.sum + ret.right.sum; } return ret; } private void update(SegmentTreeNode root, int pos, int val){ if (root.start == root.end){ root.sum = val; return; } int mid = root.start + (root.end - root.start) / 2; if (pos <= mid) update(root.left, pos, val); else update(root.right, pos, val); root.sum = root.left.sum + root.right.sum; } private int sumRange(SegmentTreeNode root, int start, int end){ if (root.start == start && root.end == end) return root.sum; else{ int mid = root.start + (root.end - root.start) / 2; if (end <= mid){ return sumRange(root.left, start, end); }else if (start >= mid + 1){ return sumRange(root.right, start, end); } else{ return sumRange(root.left, start, mid) + sumRange(root.right, mid + 1, end); } } } public NumArray(int[] nums) { root = build(nums, 0, nums.length-1); } public void update(int i, int val) { update(root, i, val); } public int sumRange(int i, int j) { return sumRange(root, i, j); } }

线段树的代码还是很简单，暂且采用递归的手段，帮助理解。