线段树
2021-10-29 本文已影响0人
_PatrickStar
线段树相关知识点梳理
- 1.线段树实现：包括add，update，query方法的实现
- 2.业务代码简单验证
- =========思路============
- 我现在面临的问题是什么？
- 1.有一个需求，需要我将数组中5~99的所有值都统统加5，那么如果按照正常的遍历去实现，时间复杂度是O(N)的。
- 2.假设这个需求调用十分频繁，可想而知会造成比较大的性能消耗。
- 所以线段树就是处理上述问题的，尤其明显的优势：如区间类的更新，累加，查询都适用。
- 先说结论；
- 线段树可以将时间复杂度降到O(logN)级别，并且需要的额外空间复杂度不会超过4*N(画图知道，堆的结构类似一个小山，从上到下铺满了也就是1，2，4，8，16这样铺下来，我们会发现及时arr长度等于N 比如=8的时候 前面的节点个数=7 我们近似看作8 这就是2N，又下面那排最大不超过2N，所以我们只需要准备一个4N的空间，绝对够用)
- 我们需要构造一个类似堆的数据；假设我们原数组内一共有4个数，下标从1-4(这里不从0开始是方便思考)
- 我们需要进行如下转换
- [3,7,5,9]=>[24,10,14,3,7,5,9] 再看一组数据
- [3,7,5,9,1] => [25,10,15,3,7,5,10,null,null,null,null,null,null,9,1]
- 我们姑且把原数组叫arr，转换后的数组叫sum(sum也是从1开始下标)
- 规律就是，先把后面的数组用堆的形势展开，然后sum[1]的位置记录的是arr[1-4]的累加和sum[2]是arr[1-2]的累加和(左孩子)
- null那些说明最后一行有些空间没有用到，但是还是分配了。结构的最后还需要写入信息。
- (当然这种遇到无法被2整除的，是让左孩子分配更多还是右孩子分配更多无所谓，看个人喜好)。比如你把1-5 分成1-3 4-5也可以。
- 基本结构有了，我们需要在分情况进行处理。
- 如果我有一个格子 存放的是2-10的累加和，那么如果新任务也是需要在2-10上加，那么就直接在这层加就好了，不需要在把2-10往下拆，继续加。
- 我们还可以引入一个数组，姑且叫做lazy。它的作用是假设之前任务是在3-29之间都加5 那么我们可以在3-29对应的数组下标同位置的lazy数组下记录一个5，
- 表示这里有一个5要累加，但是可以先不加，因为我们可以看后续还会收到什么命令。如果后续命令是累加2 那么我们直接在lazy数组那里改成7，
- 知道出现一个任务不是把3-29全包，比如出现个新任务要求在3-9之间累加6，
- 那么我们就必须先将之前lazy下来的任务下发，累加完毕，然后在根据3-9往下拆，拆到合适的位置在lazy一个6.
- 当然有可能3-9其实是由3-6，7-9拼成的。没关系，我们直接将连各个分别lazy之后最后结算的时候累加一下即可
- */
public class SegmentTree_31 {
//构造一下SegmentTree类
public static class SegmentTree {
/**
* max 原数组长度
* arr 维护一个从1开始的原数组
* sum 累加和数组 维护区间累加和
* lazy 懒数组，更新慵懒标记
* change 更新数组 维护更新情况
* update 布尔值 是否更新
* */
private int maxN;
private int[] arr;
private int[] sum;
private int[] lazy;
private int[] change;
private boolean[] update;
public SegmentTree(int[] origin){
maxN = origin.length+1;
arr = new int[maxN];
for (int i=1;i<maxN;i++){
arr[i] = origin[i-1];
}
sum = new int[maxN<<2];
lazy = new int[maxN<<2];
change = new int[maxN<<2];
update = new boolean[maxN<<2];
}
private void pushUp(int rt){
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
private void pushDown(int ln, int rn, int rt){
// 更新和累加任务如果都存在的话，肯定是要先更新 然后再累加的。所以先判断updete再去判断lazy
//下面这段代码就是说如果存在更新，那么我下面这些数组要怎么处理
if(update[rt]){
// 左右孩子的更新状态设为true
update[rt<<1] = true;
update[rt<<1|1] = true;
// 左右孩子区间更新的值为change[rt]
change[rt<<1] = change[rt];
change[rt<<1|1] = change[rt];
// 左右孩子区间累加和
sum[rt<<1] = change[rt]*ln;
sum[rt<<1|1] = change[rt*rn];
// 更新的时候，左右孩子区间lazy数组设为0
lazy[rt<<1] = 0;
lazy[rt<<1|1] = 0;
// 一定要记住吧update[rt]设为false
update[rt] =false;
}
// 如果lazy位不是0，说明之前已经懒了一些任务在这里了，这个时候要更新lazy数组和sum数组
if(lazy[rt]!=0){
lazy[rt<<1]+=lazy[rt];
lazy[rt<<1|1]+=lazy[rt];
sum[rt<<1]+=lazy[rt]*ln;
sum[rt<<1|1]+=lazy[rt]*rn;
lazy[rt]=0;
}
}
// 初始化构建sum数组,在arr[l~r]区间 去build
// l r 代表的是arr的左右区间下标 rt代表的是当前这个sum的下标，这个位置的sum 囊括的就是arr[l~r]的累加和
// 分情况考虑l=r 和l！=r
private void build(int l, int r, int rt){
if (l==r){
sum[rt] = arr[l];
return;
}
int mid = (l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushUp(rt);
}
//L ,R ,C 参数代表整个累加任务是从L到R区间，每个数加个C
//l r rt参数代表从最初任务一路往下拆下来，当前的sum节点，rt代表他的下标，l,r分别记录了他所囊括的arr是l-r的区间
private void add(int L, int R, int C,int l, int r, int rt){
if(L<=l&&r<=R){
//说明当前所在的sum节点是完全被任务所包围的，比如我任务是要在1-9区间加个5，现在这个位置是2-7
sum[rt]+=C*(r-l+1);
lazy[rt]+=C;
return;
}
int mid = (l+r)>>1;
//先pushDown,将左右孩子区间的sum lazy数据先更新正确
pushDown(mid-l+1,r-mid,rt);
if(L<=mid){
add(L,R,C,l,mid,rt<<1);
}
if (R>mid){
add(L,R,C,mid+1,r,rt<<1|1);
}
pushUp(rt);
}
private void update(int L, int R, int C,int l, int r, int rt){
if(L<=l&&r<=R){
//说明当前所在的sum节点是完全被任务所包围的，比如我任务是要在1-9区间统一更新成5，现在这个位置是2-7
update[rt] = true;
change[rt] = C;
sum[rt]=C*(r-l+1);
lazy[rt]=0;
return;
}
int mid = (l+r)>>1;
//先pushDown,将左右孩子区间的sum lazy数据先更新正确
pushDown(mid-l+1,r-mid,rt);
if(L<=mid){
update(L,R,C,l,mid,rt<<1);
}
if (R>mid){
update(L,R,C,mid+1,r,rt<<1|1);
}
pushUp(rt);
}
// 因为查询不需要修改数据 所以省去了参数C
private long query(int L, int R,int l, int r, int rt){
if(L<=l&&r<=R){
return sum[rt];
}
int mid = (l+r)>>1;
//先pushDown,将左右孩子区间的sum lazy数据先更新正确
pushDown(mid-l+1,r-mid,rt);
long ans = 0;
if(L<=mid){
ans+=query(L,R,l,mid,rt<<1);
}
if (R>mid){
ans+=query(L,R,mid+1,r,rt<<1|1);
}
return ans;
}
}
// 写一个业务代码用做对数器
public static class Right{
private int[] arr;
public Right(int[] origin){
arr = new int[origin.length+1];
for (int i=1;i<arr.length;i++){
arr[i] = origin[i-1];
}
}
public void add(int L,int R,int C){
for(int i=L;i<=R;i++){
arr[i] = arr[i]+C;
}
}
public void update(int L,int R,int C){
for(int i=L;i<=R;i++){
arr[i] = C;
}
}
// 查询l-r上的累加和
public long query(int L,int R){
long ans = 0;
for(int i=L;i<=R;i++){
ans+=arr[i];
}
return ans;
}
}
//写个测试
public static void main(String[] args) {
int[] origin = new int[]{3,5,6,-5,58,9,5};
SegmentTree segmentTree = new SegmentTree(origin);
Right right = new Right(origin);
segmentTree.build(0, origin.length, 1);
long num1 = segmentTree.query(2, origin.length-1,0, origin.length, 1);
long num2 = right.query(2,origin.length-1);
System.out.println(num1);
System.out.println(num2);
System.out.println(num1==num2);
}
}
