【leetcode】线段树

1. 线段树入门

本文主要参考自jiayi797的专栏JustDoIT线段树知识点总结

线段树,类似区间树,它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操作的复杂度为O(logn)。

线段树的每个节点表示一个区间,子节点则分别表示父节点的左右半区间,例如父亲的区间是[a,b],那么(c=(a+b)/2)左儿子的区间是[a,c],右儿子的区间是[c+1,b]。线段树形如:

img

下面我们从一个经典的例子来了解线段树,问题描述如下:从数组arr[0…n-1]中查找某个数组某个区间内的最大值,其中数组大小固定,但是数组中的元素的值可以随时更新。从这题可以看出:区间(a,b)的最大值和区间(b,c)的最大值中,取较大的就是区间(a,c)的最大值。很明显这个操作具有区间的性质。

我们可以用线段树来解决这个区间最大值问题。根据这个问题我们构造如下的二叉线段树。区间的第三维就是区间的最大值。

img

加入第三维的时候,只需要在构建完左右区间后,根据左右区间的最大值更新当前区间最大值即可。

因为每次将区间长度一分为二,所有构造的节点个数为:

n + 1/2 n + 1/4 n + 1/8 * n + …

= (1 + 1/2 + 1/4 + 1/8 + …) * n

= 2n

所以构造线段树的时空复杂度都为O(n)。

1.1. 线段树常见题型

一道题可不可以用线段树来做,基本是看这道题的操作有没有区间的性质。也就是在一个区间上的操作是否可以转化为两个子区间上的操作。

  • 求区间和,积,最小值,gcd等
  • 以当前节点的值作为节点处理。例如给出N个数字,再给一个数,问比这个数大的有多少个。
  • 区间加减同一个值,或者区间同时赋一个值。

1.2. 链式线段树

我们常见的二叉树都是链式结构。因此我们先完成链式的线段树。

建树

复杂度O(n)

public class SegmentTree {
//线段树节点定义
public class SegmentTreeNode{
int start;
int end;
int max;
SegmentTreeNode left = null;//定义左右节点
SegmentTreeNode right = null;
SegmentTreeNode(int start,int end,int max){
this.start = start;
this.end = end;
this.max = max;
}
}
public SegmentTreeNode builder(int[] A){
return helper(0,A.length-1,A);
}
public SegmentTreeNode helper(int low,int high,int[] A){
if (low > high){
return null;
}
SegmentTreeNode root = new SegmentTreeNode(low,high,A[low]);
if(low == high){
return root;
}
else{
root.left = helper(low,high/2,A);
root.left = helper(high/2+1,high,A);
root.max = Math.max(root.left.max,root.right.max);//更新当前节点max值
}
return root;
}
}

区间查询

复杂度 O(log(n))O(log(n))

构造线段树目的是为了更快地查询。例如给定区间,要求区间中的最大值。而线段树的区间查询操作就是将当前区间分解为较小的子区间,然后由子区间的最大值就可以快速得到需要查询区间的最大值。例如

query(1,3) = max(query(1,1), query(2,3)) = max(4,3) = 4

查询实现:

//在线段树中查找[low,high]区间的最大值
public int query(SegmentTreeNode root,int low,int high){
if(root.start == low && root.end == high){
return root.max;
}
int mid = (root.start + root.end) / 2;
int result = Integer.MIN_VALUE;
if(mid >= low){//查询区间与左半区间有交集,最大值有可能在左半区间
result = Math.max(result,query(root.left,low,mid));
}
if(mid+1 <= high){ //查询区间与右半区间有交集,最大值有可能在右半区间
result = Math.max(result,query(root.right,mid+1,high));
}
return result;
}

单点更新

复杂度 O(log(n))O(log(n))

更新序列中的一个节点,那么如何把这种变化体现到线段树中呢?

img

例如要将第4个点更新为5.就要变动3个区间的值,分别为[3,3], [2,3], [0,3]

img

改动一个节点,与这个节点对应的叶子结点都要变动。并且,这个节点变动后,这个节点的属性值也有可能会变动,那么就有可能影响到这个节点的父亲节点的属性值(例如可能影响到最大值)。所以需要从叶子节点一路走到根节点。

单点更新实现:

public void modify(SegmentTreeNode root,int idx,int val){
////如果找到相应叶子节点了
if(root.start == root.end && root.start == idx){
root.max = val;//修改max值
return;
}
int mid = (root.start + root.end) / 2;
if(idx <= mid){//要修改的在左边
modify(root.left,idx,val);
}
else {
modify(root.right,idx,val);
}
//跟新root的max
root.max = Math.max(root.left.max,root.right.max);
}