
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