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

树链剖分/轻重链剖分

基础封装(配合线段树等数据结构使用)

本封装将线段树处理的部分分离,方便修改。支持模板题P3384 【模板】重链剖分/树链剖分的四个查询(链上查询/修改、子树查询/修改),建树时间复杂度 O(Nlog⁡N)\mathcal O(N\log N) ,单次查询时间复杂度 O(log2⁡N)\mathcal O(\log ^2 N) 。

struct HLD {int n, idx;vector<vector<int>> ver;vector<int> siz, dep;vector<int> top, son, parent;vector<int> in, id, val;Segt segt;HLD(int n) {this->n = n;ver.resize(n + 1);siz.resize(n + 1);dep.resize(n + 1);top.resize(n + 1);son.resize(n + 1);parent.resize(n + 1);idx = 0;id.resize(n + 1);val.resize(n + 1);}void add(int x, int y) { // 建立双向边ver[x].push_back(y);ver[y].push_back(x);}void dfs1(int x) {siz[x] = 1;dep[x] = dep[parent[x]] + 1;for (auto y : ver[x]) {if (y == parent[x]) continue;parent[y] = x;dfs1(y);siz[x] += siz[y];if (siz[y] > siz[son[x]]) {son[x] = y;}}}void dfs2(int x, int up) {id[x] = ++idx;val[idx] = in[x]; // 建立编号top[x] = up;if (son[x]) dfs2(son[x], up);for (auto y : ver[x]) {if (y == parent[x] || y == son[x]) continue;dfs2(y, y);}}void work(int root, auto in) { // 在此初始化this->in = in;dfs1(root);dfs2(root, root);segt.init(val); // 建立线段树}void modify(int l, int r, int val) { // 链上修改while (top[l] != top[r]) {if (dep[top[l]] < dep[top[r]]) {swap(l, r);}segt.modify(id[top[l]], id[l], val);l = parent[top[l]];}if (dep[l] > dep[r]) {swap(l, r);}segt.modify(id[l], id[r], val);}void modify(int root, int val) { // 子树修改segt.modify(id[root], id[root] + siz[root] - 1, val);}int ask(int l, int r) { // 链上查询int ans = 0;while (top[l] != top[r]) {if (dep[top[l]] < dep[top[r]]) {swap(l, r);}ans += segt.ask(id[top[l]], id[l]);l = parent[top[l]];}if (dep[l] > dep[r]) {swap(l, r);}return ans + segt.ask(id[l], id[r]);}int ask(int root) { // 子树查询return segt.ask(id[root], id[root] + siz[root] - 1);}
};

模板题

P3384 【模板】重链剖分/树链剖分

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

相关文章:

  • 如何降低信息化系统的构建成本? ——信息化系统省钱全攻略:从规划到运维的实用技巧
  • C#编程时winform程序登陆记住密码和自动登录功能,关于App.config的问题及解决方案
  • 2025.10.23总结
  • Day2超链接标签
  • Ai元人文构想:你喜欢黑箱与偏见
  • 企业微信 使用api批量处理群消息
  • first game (1)
  • 10月23日日记
  • Gin笔记一之项目建立与运行
  • 软件工程学习日志2025.10.23
  • 10月23号
  • 【题解】P14254 分割(divide)
  • 数论分块 - R
  • 第九届强网杯线上赛PWN_flag-market
  • ISFB银行木马家族演化史:从Gozi到LDR4的技术剖析
  • 10.23日学习笔记
  • 埃氏筛及扩展质因数筛——埃拉托斯特尼筛法变种
  • exgcd板子
  • 2025.10.23
  • 编程练习
  • Codeforces Round 976 (Div. 2) A. Find Minimum Operations
  • 手机号md5解密/身份证号码md5解密/手机号运营商+归属地查询
  • 102302142罗伟钊第一次作业
  • 一个基于 .NET 开源、功能强大的分布式微服务开发框架
  • UE4学习笔记
  • 20251021 NOIP模拟赛
  • 关于2025年暑假自主巡航小车脚本文件的学习笔记
  • 欧拉操作系统搭建docker
  • xcode程序创建文件存储位置
  • RocketMQ+Spring Boot的简单实现及其深入分析