区间操作：差分与线段树 详细讲解

在算法和编程中区间操作给一段区间的数统一加减、查询区间和 / 单点值是高频考点差分和线段树是解决这类问题的两个核心工具。目录一、什么是区间操作二、差分Difference Array1. 核心思想2. 原理3. 适用场景4. 简单例子三、线段树Segment Tree1. 核心思想2. 适用场景3、用什么来存储区间片段4. 关键技术懒标记lazy tag5、核心结构6、总结线段树的执行流程四、差分 vs 线段树 对比一、什么是区间操作常见需求区间修改对[L, R]内所有数 加k 或者 减k单点查询多次区间修改之后问第 i 个数是多少区间查询求[L, R]的总和 / 最大值 / 最小值二、差分Difference Array1. 核心思想差分 区间修改神器只能做区间加减 单点查询通常把对区间的操作变成对两个点的操作把O (n) 的区间修改变成O(1)最后用 O (n)还原数组2. 原理原数组a[1...n]差分数组d[1...n]定义d[1] a[1]d[i] a[i] - a[i-1] (i1)如果要对【L,R】区间的数加k则只需对差分数组进行加减最后通过求前缀和还原数组d[L] k d[R1] - k多次修改就是把对差分数组的修改放到循环里全部修改完毕之后再统一还原数组前缀和还原修改后的数组//就是对差分数组进行前缀和求解 int[] res new int[n 1]; for (int i 1; i n; i) { res[i] res[i - 1] diff[i]; }3. 适用场景大量区间修改 最后一次性查询不支持区间和查询、区间最大值查询4. 简单例子原数组[0, 1, 2, 3, 4]对[2,4] 5差分数组d2【01111】差分操作d[2] 5d[5]-5操作后差分数组d2【01611】最后还原[0,1,7,8,9]三、线段树Segment Tree1. 核心思想线段树 全能型区间数据结构线段树是把一个数组拆成很多个「区间片段」用树结构存储这些区间实现高效的区间修改 区间查询。普通数组做区间操作是 (O(n))线段树能做到 (O(logn))处理大数据量1e5/1e6不会超时。支持区间修改、区间总和/最值查询、单点修改、单点查询所有操作都是O(log n)2. 适用场景边修改边查询修改和查询交替进行需要区间和 / 区间最大值 / 区间最小值3、用什么来存储区间片段用Node节点每一个Node节点代表一段区间static class Node { int l, r; // 节点管的区间 [l, r] long sum; // 区间和 int add; // 懒标记区间加法的延迟标记 int min; // 区间最小值优化取min int max; // 区间最大值优化取min }4.关键技术懒标记lazy tag区间修改时先标记不下传等到必须访问子节点时再更新保证效率。5、核心结构1、build 建树把数组建成区间树存好每个区间和实现思路二分递归不断把一个大区分二分为左右两个区间分到叶子节点lr直接赋值数组元素非叶子节点用子节点信息合并自己的值pushUpstatic void build(int u, int l, int r) { tr[u] new Node(); tr[u].l l; tr[u].r r; if (l r) { // 叶子节点直接存原值 tr[u].sum a[l]; tr[u].min a[l]; tr[u].max a[l]; return; } // 二分 int mid (l r) / 2; build(u*2, l, mid); // 左孩子 build(u*21, mid1, r); // 右孩子 pushUp(u); // 用孩子更新自己 }2、pushup 向上更新子节点变了父节点重新算和子节点 → 父节点父节点的 sum/min/max 完全由左右两个孩子计算而来。区间和 左和 右和区间最小值 左 min、右 min 取小区间最大值 左 max、右 max 取大static void pushUp(int u) { tr[u].sum tr[u*2].sum tr[u*21].sum; tr[u].min Math.min(tr[u*2].min, tr[u*21].min); tr[u].max Math.max(tr[u*2].max, tr[u*21].max); }3、pushdown 下传懒标记每次在访问子节点之前需要把之前攒的修改下发用来更新子节点。下传之后需清空父节点的懒标记static void pushDown(int u) { if (tr[u].add ! 0) { int add tr[u].add; // 传给左孩子 tr[u*2].sum (long)add * 长度; tr[u*2].min add; tr[u*2].max add; tr[u*2].add add; // 传给右孩子 tr[u*21].sum (long)add * 长度; tr[u*21].min add; tr[u*21].max add; tr[u*21].add add; tr[u].add 0; // 清空标记 } }5 、区间操作区间加、区间最小值、区间求和遵循统一递归逻辑分为三种情况无交集、全包含、部分相交1. 如果当前区间 和 目标区间 无交集 → 直接返回 2. 如果当前区间 完全包含在 目标区间内 → 直接修改/返回值 3. 否则就是部分相交 → 先 pushDown再递归左右孩子最后 pushUp1区间加public static void rangeAdd(int u, int l, int r, int x) { if (tr[u].r l || tr[u].l r) return; if (l tr[u].l tr[u].r r) { tr[u].sum (long) x * (tr[u].r - tr[u].l 1); tr[u].min x; tr[u].max x; tr[u].add x; return; } pushDown(u); rangeAdd(u * 2, l, r, x); rangeAdd(u * 2 1, l, r, x); pushUp(u); }2区间最小值public static void rangeMin(int u, int l, int r, int x) { if (tr[u].r l || tr[u].l r) return; if (tr[u].max x) return; // 整个区间都比x小不用改 if (l tr[u].l tr[u].r r tr[u].min x) { // 整个区间都比x大直接变成x int cnt tr[u].r - tr[u].l 1; tr[u].sum (long) x * cnt; tr[u].min x; tr[u].max x; tr[u].add 0; // 之前的add标记失效了 return; } pushDown(u); rangeMin(u * 2, l, r, x); rangeMin(u * 2 1, l, r, x); pushUp(u); }3区间求和public static long querySum(int u, int l, int r) { if (tr[u].r l || tr[u].l r) return 0; if (l tr[u].l tr[u].r r) return tr[u].sum; pushDown(u); return querySum(u * 2, l, r) querySum(u * 2 1, l, r); }注意所有递归操作前必须先 pushDown否则子节点数据还是旧的会出错。而每次做完区间操作之后就要pushUp把子节点的最新数据重新汇总更新父节点往上同步刷新6、总结线段树的执行流程建树 ↓ 每次操作 1. 无交集 → 退出 2. 全包含 → 直接修改/查询 3. 有交集 → pushDown递归左右pushUp四、差分 vs 线段树 对比特性差分线段树区间修改O (1) 极快O (log n) 快区间查询不支持支持和 / 最值单点查询最后 O (n) 还原O(log n)代码难度简单中等适用场景批量修改最后查值边改边查需要区间和只做区间加减 最后查单点→ 用差分需要边改边查 / 区间和→ 用线段树