当前位置: 首页 > news >正文

树状数组和线段树基础

本文代码适用于c++

树状数组

问题引入

思考这样一个问题:对于给定的数组[1,n],多次询问[l,r]的区间和。
当然,我们可以用前缀和sum[r]-sum[l-1],这是因为区间和减法的好性质。
下面我们介绍一种时间复杂度为(log n)的,针对一维数组前缀查询问题的高效数据结构

对树状数组的简单理解

  1. 树状数组通过将[1,n]分割为个数小于[log n]的许多个子区间,通过维护子区间来实现功能。

  2. 我们定义一个辅助数组c:c[x]是以x为右边界的子区间的特征值

  3. 原理图示(图中特征值为区间和)

联想截图_20251019163113

  1. 树状数组的查询:设l(x)为c[x]的左边界

查询[1,x]的过程如下

从c[x]到l(x)
令x=l(x)-1,再次重复上述过程,直到x=1;

  1. 下面我们来具体确定这个l(x)

树状数组的实现

1. lowbit函数

lowbit(x)=2k, 其中k是满足在二进制下x第k位是1的最小整数

二进制及位运算https://www.cnblogs.com/Ahui2667d/p/19139524

根据定义和位运算:lowbit(x)=x&-x.

对于c[x],它所管辖的区间长度为lowbit(x)。它所管辖的区间为[x-lowbit(x)+1,x]

下面给出lowbit(x)的一些简单性质:

  1. 若x<=y,那么c[x]要么与c[y]不交,要么包含于c[y]。
  2. c[x]真包含于c[x+lowbit(x)]
  3. 若x<y<x+lowbit(x), 则c[y]与c[x]不交

2. 树状数组的单点修改

显然的, 若x改变,那么c[i]中c[x]的一切母集也要改变

代码实现
void add(int x, int y )//对x点加y
{for (; x <= n; x += x & -x)c[x] += y;
}

我们可以利用上述代码建树

for (int i = 1; i <= n; i++){int x;cin >> x;add(i, x);}

3. 树状数组的区间查询

对于[l,r]将其转化为[1,l]和[1,r]的情况

代码实现
int ask(int x)//返回[1,x]的区间和
{int y = 0;for (; x; x -= x & -x)y += c[x];return y;
}

简单总结:树状数组善于解决的问题

树状数组善于解决一维数组的部分区间特征值问题
一般这个特征值满足可差分,有结合律的特点

举例:区间和 区间乘法 区间查询 单点修改
区间修改 单点查询(只需将差分数列存储到c[x]进行单点修改即可)

线段树

接下来我们介绍一种代码实现稍复杂但是适用度更广的数据结构:线段树

线段树的简单理解

简单说,线段树就是通过将长度非一的区间二分递归以维护区间特征值的方法。

图示
image

线段树的实现

结合图示, 不难观察到d[x]的左儿子是d[2x]右儿子是d[2x+1]

1.建树

void build(int l, int r, int p)//建立[l,r]的线段树,当前节点为p
{if (l == r)d[p] = a[l];else{int mid = l + ((r - l) >> 1);build(l, mid, p << 1);build(mid + 1, r, (p << 1) +1);d[p] = d[2 * p] + d[2 * p + 1];}
}

2. 区间查询

//查询[l,r]的区间和
nt getsum(int l, int r, int s, int t, int p)//目前访问[s,t]区间,p节点
{if (l <= s && r >= t)//查询区间就在访问的区间内return d[p];else{int sum = 0;int m = s + ((t - s) >> 1);if (m >= r)//[l,r]与左儿子有交sum += getsum(l, r, s, m, 2 * p);if (m + 1 <= l)//与右儿子有交sum += getsum(l, r, m + 1, t, 2 * p + 1);return sum;}
}

3.区间修改

如果每进行一次区间修改都从某个根节点遍历到叶子,显然时间复杂度太高。我们想办法优化:使得不询问某个子节点就不必在修改时遍历他.

懒惰标记

承接上面的思想,我们回过头来看那张图示

image

假如我们要对[3,5]进行修改,我们可以找组成[3,5]的几个最大子区间,即3,3和4,5。因为如果要遍历某一个字节,它的父节点一定被遍历,于是我们可以对修改过的父节点进行标记,当我们遍历到这个有标记的节点时候提醒我们它的子节点也要进行修改。

这个标记我们称之为懒惰标记

代码实现
//将[l,r]内的元素都加c,正在访问[s,t],节点p
void update(int l, int r, int c, int s, int t, int p)
{if (l <= s && t <= r){d[p] += c * (t - s + 1);b[p] += c;return ;}int m = s + ((t - s) >> 1);if (b[p] && t - s)//实际上这里的t-s>0的判断是多余的,因为如果t==s的话,它一定在[l,r]中{d[2 * p] += (m - l + 1) * c, d[2 * p + 1] += (r - m) * c;b[2 * p] += c, b[2 * p + 1] += c;}if (l <= m) update (l, r, c, s, m, 2 * p);if (r >= m + 1) update (l, r, c, m + 1, t, 2 * p + 1);d[p] = d[p * 2 + 1] + d[p * 2];
}

线段树的一些优化

  1. 当我们不需要询问某个节点时候,可以不对它和它的子节点建树
  2. 叶子处无需下放懒惰标记
  3. 可以写一个函数putdown来实现懒惰标记下放的操作以减少编码难度.
http://www.hskmm.com/?act=detail&tid=34512

相关文章:

  • C++ofstream写文件bug
  • Debian13中使用Virtual-box安装Window10虚拟机并设置USB直通
  • 2024长城杯决赛-溯源取证1
  • [Agent] ACE(Agentic Context Engineering)和Dynamic Cheatsheet学习笔记
  • 2025年9月模拟赛整合
  • 软工问题总结10.19
  • AI元人文构想研究:理论溯源、跨学科审视与技术路径探析
  • NOAI官方学术支持
  • 【ARM CoreLink 系列 4.1 -- NI-700 interconnect hub 控制器详细介绍】
  • NPM(更新中)
  • 使用DAO模式改造学生信息管理系统
  • 【ARM CoreLink 系列 4 -- NIC-400 控制器详细介绍】
  • Linux反弹shell解析
  • 2025-10-18 MX-S 模拟赛 赛后总结【MX】
  • P1854 花店橱窗布置 解题笔记
  • P1896[SCOI2005]互不侵犯 解题笔记
  • habse
  • hbase
  • 微信小程序 在云函数本地调试时,总是提示node modules 未安装,立即安装。解决方法
  • Godot-C#场景之间的切换
  • 读书日记1
  • 【ARM CoreLink 系列 3.1 -- CCI-500 详细介绍 -上半部】
  • 央企程序员AI创业一个月感受 ✨
  • tryhackme-预安全-网络基础知识-局域网介绍-05
  • 10.19
  • 从众多知识汲取一星半点也能受益匪浅【day16(2025.10.18)】(加班但只加到四点半)
  • (个人思考)游戏技能的实现
  • 模拟赛T4 分析
  • ubuntu系统中containerd的cni网络配置
  • 十月阅读笔记