mzoe666888

V1

2022/06/06阅读:30主题:兰青

内卷大厂系列《线段树》

《线段树/树状数组》,您将学到线段树能解决什么问题以及运用场景,如何快速实现整体批量更新修改、批量查询,线段树是不错的选择。

一、介绍

线段树也称树状数组,主要解决什么问题呢?

线段树是一种支持范围整体修改范围整体查询的数据结构

方法一:通过遍历的方式修改和查询,时间复杂度O(N)

方法二:通过线段树实现,时间复杂度O(logN)

如果让你提供一种服务,范围内整体更新或范围内整体查询,而且访问量比较大,你会怎么设计?从时间复杂度上看,当然选O(logN)了,这时候线段树就能帮你解决这种问题了。

如下说明线段树需要实现的功能:

给定一个数组arr,用户希望你实现如下三个方法

  • void add(int L, int R, int V) : 让数组arr[L…R]上每个数都加上V
  • void update(int L, int R, int V) : 让数组arr[L…R]上每个数都变成V
  • int sum(int L, int R) : 让返回arr[L…R]这个范围整体的累加和

怎么让这三个方法,时间复杂度都是O(logN)

二、分析

线段树的实现有非递归版本实现,但有些麻烦!!!

线段树的递归方法实现,不用担心栈会溢出情况,因为不可能那么大

假设有 N = 2^26 规模的数据,这已经很大了,那么logN = 64,也就64次搞定

把数组转换成一个树状结构,规定数组下标从1开始,容易理解,正常数组下标是从0开始的

数组转换成二叉树结构:

申请一个数组空间,里边放格子,0位置不用,再把数组进行转换成二叉树结构:

新数组的任何格子节点都能找到它的父节点,公式为:i/2

i格子信息:

  • 父节点:i/2
  • 左孩子:2*i
  • 右孩子:2*i + 1

有了这个公式,就知道任何格子在哪个位置,也知道当前格子的父节点在哪,左孩子在哪,右孩子在哪

当一个任务到来时,往下发的过程,卡主一个左边界,卡主一个右边界,涉及到懒更新停止下发,只要不全包就下发

懒更新:当前格子任务的起始和结束位置在下发任务的起始和结束范围内,就是任务被包住了,停止下发给下边的格子,用一个懒格子记录起来

三、实现

public static class SegmentTree {
  // arr[]为原序列的信息从0开始,但在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]; // arr[0] 不用 从1开始使用
    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];
  }

  // 之前的,所有懒增加,和懒更新,从父范围,发给左右两个子范围
  // 分发策略是什么
  // ln表示左子树元素结点个数,rn表示右子树结点个数
  private void pushDown(int rt, int ln, int rn) {
    if (update[rt]) {
      update[rt << 1] = true;
      update[rt << 1 | 1] = true;
      change[rt << 1] = change[rt];
      change[rt << 1 | 1] = change[rt];
      lazy[rt << 1] = 0;
      lazy[rt << 1 | 1] = 0;
      sum[rt << 1] = change[rt] * ln;
      sum[rt << 1 | 1] = change[rt] * rn;
      update[rt] = false;
    }
    if (lazy[rt] != 0) {
      lazy[rt << 1] += lazy[rt];
      sum[rt << 1] += lazy[rt] * ln;
      lazy[rt << 1 | 1] += lazy[rt];
      sum[rt << 1 | 1] += lazy[rt] * rn;
      lazy[rt] = 0;
    }
  }

  // 在初始化阶段,先把sum数组,填好
  // 在arr[l~r]范围上,去build,1~N,
  // rt : 这个范围在sum中的下标
  public 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  rt
  public void update(int L, int R, int C, int l, int r, int rt) {
    if (L <= l && r <= R) {
      update[rt] = true;
      change[rt] = C;
      sum[rt] = C * (r - l + 1);
      lazy[rt] = 0;
      return;
    }
    // 当前任务躲不掉,无法懒更新,要往下发
    int mid = (l + r) >> 1;
    pushDown(rt, mid - l + 1, r - mid);
    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);
  }

  // L~R, C 任务!
  // rt,l~r
  public void add(int L, int R, int C, int l, int r, int rt) {
    // 任务如果把此时的范围全包了!
    if (L <= l && r <= R) {
      sum[rt] += C * (r - l + 1);
      lazy[rt] += C;
      return;
    }
    // 任务没有把你全包!
    // l  r  mid = (l+r)/2
    int mid = (l + r) >> 1;
    pushDown(rt, mid - l + 1, r - mid);
    // L~R
    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);
  }

  // 1~6 累加和是多少? 1~8 rt
  public 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(rt, mid - l + 1, r - mid);
    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;
  }

}

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1