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

[线段树系列 #6] 标记永久化

[线段树系列 #6] 标记永久化

标记永久化是线段树的一个技巧,通常用于对主席树等难以 pushdown 的数据结构进行区间修改

具体思想已经体现在名字里了,我们结合例题稍微讲解一下

例题1

P3372 【模板】线段树 1

线段树区间修改区间查询板子

void modify(ll p, ll l, ll r, ll v) {t[p].sum += (min(t[p].r, r)-max(t[p].l, l)+1)*v;if(l <= t[p].l && t[p].r <= r) {t[p].add += v;return;}ll mid = (t[p].l+t[p].r) >> 1;if(l <= mid) modify(p*2, l, r, v);if(mid < r) modify(p*2+1, l, r, v);
}
ll query(ll p, ll l, ll r, ll ad) {if(l <= t[p].l && t[p].r <= r) return t[p].sum+ad*(t[p].r-t[p].l+1);ll mid = (t[p].l+t[p].r) >> 1, res = 0;if(l <= mid) res += query(p*2, l, r, ad+t[p].add);if(mid < r) res += query(p*2+1, l, r, ad+t[p].add);return res;
}
// 剩余部分与普通线段树一致

可见,每个线段树节点上新增了 \(add\) 值,具体细节很显然,但这没有 pushdown 函数,并且维护了区间修改操作。但是标记永久化不能维护先后顺序(如线段树 2 中的乘加操作)和交换律。

例题2

SP11470 TTM - To the moon

主席树区间修改

void modify(ll &p, ll q, ll l, ll r, ll L, ll R, ll v) {p = ++cnt;t[p] = t[q];t[p].sum += (min(R, r)-max(L, l)+1)*v;if(L <= l && r <= R) {t[p].add += v;return;}ll mid = (l+r) >> 1;if(L <= mid) modify(t[p].l, t[q].l, l, mid, L, R, v);if(mid < R) modify(t[p].r, t[q].r, mid+1, r, L, R, v);
}
ll query(ll p, ll l, ll r, ll L, ll R, ll ad) {if(L <= l && r <= R) return t[p].sum+ad*(r-l+1);ll mid = (l+r) >> 1, res = 0;if(L <= mid) res += query(t[p].l, l, mid, L, R, ad+t[p].add);if(mid < R) res += query(t[p].r, mid+1, r, L, R, ad+t[p].add);return res;
}

和线段树同理

2025.9.29 19:10

http://www.hskmm.com/?act=detail&tid=21055

相关文章:

  • 9.29
  • c语言switch和if语句
  • Qt(制作一个方便的文本编辑器)
  • Java EE初阶启程记05---线程安全 - 指南
  • DataGridView表格控件使用说明
  • 题解:P7126 [Ynoi2008] rdCcot
  • 个人微信机器人开发api接口
  • MyBatis技术详解:从入门到高效开发 - 详解
  • 解码数据结构队列
  • 解决升级 Windows 11 24H2 后 NAS 共享无法显示的问题
  • 【还未找到原题】宝石(GEM) - Harvey
  • 第八篇
  • C# AStar 算法 - 实际应用
  • nocobase 源码安装
  • 航司网站url后缀参数FECU分析
  • 子网掩码完全指南:从入门到精通
  • 微信群机器人API
  • 9月29号
  • 【CF19E】Fairy - Harvey
  • Python从入门到实战 (14):工具落地:用 PyInstaller 打包 Python 脚本为可执行文件 - 实践
  • Harmony实现流转开发之音乐播放器跨设备流转 - 实践
  • 软件工程中线性回归应用
  • 解决秒杀高并发的一些方案
  • 构建移动网关:Air780EPM用4G为WiFi和LAN设备供网
  • 9.29模拟赛总结
  • 多corner综合
  • 优化 if/else 的四种设计模式
  • Day11-C:\Users\Lenovo\Desktop\note\code\JavaSE\Basic\src\com\oop\demo06
  • 牛客周赛 Round 111
  • OpenLayers地图交互 -- 章节十一:拖拽材料交互详解