算法细节系列（28）：线段树
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434798
算法细节系列（28）：线段树
详细代码可以fork下Github上leetcode项目，不定期更新。
题目摘自leetcode：
Leetcode 307. Range Sum Query - Mutable
解法1
这题的特色在于不断更新的numsi，所以我们在用累加和进行求解时，每当update一次，都需要更新sums一次，虽然sumRange的复杂度为O(1)O(1)，但更新的复杂度为O(n)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
想更新就直接更新numsi，在sumRange操作时，直接累加i到j的所有元素，所以更新的时间复杂度为O(1)O(1)，而求和的时间复杂度为O(n)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)O(n)，当然这是均摊下来的。
究其原因在于累加和区间之间的关系太过强烈，一些简单的想法。
- 不要让区间之间的关系太强烈，那么就让区间与区间尽量独立。
再看方法2，区间之间的关系太独立了，每个元素代表一个点，以至于我们在sumRange时，需要把所有在范围(i,j)的区间加进来。
此时有了另外一个想法：
- 分别以两个点表示一个区间，这样更新两个点的任何一个，都不会影响任何其他区间。
好想法，那如何求任何范围内的sum(i,j)呢？再用单个点表示一个区间呗。
如：
nums = [1,2,3,4]可以表示成：
我们用index来表示每个结点，也就是区间。这样一来，更新变得独立了，更新点1时，只会影响它的父结点，而周围的兄弟结点不会受到任何影响，更新相比较于方法1要独立的多。
所以更新的操作从原来的O(1)O(1)变成了O(logn)O(\log n)，再来看看sum求和操作，这种情况求和是关键。
给定求和范围(i,j)，运气最好，直接求(1,4)的和，直接返回，但运气最差，一定会沉降到树底，但由于它是分治方法，树的深度最大也是logn\log n，所以求和最多也是O(logn)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);
}
}线段树的代码还是很简单，暂且采用递归的手段，帮助理解。
腾讯云开发者
