树链剖分/轻重链剖分

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

本封装将线段树处理的部分分离，方便修改。支持模板题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 【模板】重链剖分/树链剖分