洛谷模板题已过【P2617 Dynamic Rankings】
/* 动态持久化线段树（树状数组套线段树）模板类* 用于解决带修改的区间第k小和区间排名查询问题* 核心功能：* - 单点更新 O(log n log V)* - 区间第k小查询 O(log n log V)* - 区间排名查询 O(log n log V)*/
template<class Node>
struct DynamicPersistentSegmentTree {int n; // 原数组大小（树状数组大小）int V; // 离散化后的值域范围 [1, V]int tot = 0; // 线段树节点计数器vector<Node> tr; // 线段树节点池vector<int> roots; // 树状数组的根节点数组(下标1~n)vector<int> arrL,arrR; // 临时存储树状数组路径节点DynamicPersistentSegmentTree(int n_, int V_) : n(n_), V(V_) {tr.reserve(n * __lg(n) * __lg(V) * 4);tr.resize(1);tr[0] = Node();roots.assign(n + 1, 0);}/* 单点更新操作* @param pos: 原数组位置 (1-indexed)* @param val: 离散化后的权值* @param w: 更新值* 时间复杂度：O(log n * log V)*/void update(int pos, int val, int w) {// 树状数组遍历：更新所有包含pos的线段树for (int i = pos; i <= n; i += i & -i) {roots[i] = insert(roots[i], 1, V, val, w);}}/* 区间第k小查询* @param l: 区间左端点 (1-indexed)* @param r: 区间右端点 (1-indexed)* @param k: 查询的排名* @return: 离散化后的权值* 时间复杂度：O(log n * log V)*/int query_kth(int l, int r, int k) {get_roots(l - 1, arrL);get_roots(r, arrR);return query_kth(arrL, arrR, k, 1, V);}/* 区间排名查询（小于x的数的个数）* @param l: 区间左端点* @param r: 区间右端点* @param x: 离散化后的权值* @return: 排名值* 时间复杂度：O(log n * log V)*/int query_rank(int l, int r, int x) {get_roots(l - 1, arrL);get_roots(r, arrR);return query_rank(arrL, arrR, 1, V, x);}private:int insert(int now, int l, int r, int pos, int w) {if (!now) {now = ++tot; tr[now] = Node(); }tr[now].v += w; if (l == r) {return now; }int mid = (l + r) >> 1; if (pos <= mid) {tr[now].l = insert(tr[now].l, l, mid, pos, w);}else {tr[now].r = insert(tr[now].r, mid + 1, r, pos, w);}return now;}void get_roots(int x, vector<int>& arr) {arr.clear();while (x) {arr.push_back(roots[x]);x -= x & -x;}}int query_kth(vector<int>& arrL, vector<int>& arrR, int k, int l, int r) {if (l == r) {return l;}int mid = (l + r) >> 1;int sum = 0;// 计算左子树的总和（右区间和 - 左区间和）for (int i : arrR) {sum += tr[tr[i].l].v; // 累加右区间左子树}for (int i : arrL) {sum -= tr[tr[i].l].v; // 减去左区间左子树}if (k <= sum) {for (int& i : arrL) {i = tr[i].l;}for (int& i : arrR) {i = tr[i].l;}return query_kth(arrL, arrR, k, l, mid);}else {for (int& i : arrL) {i = tr[i].r;}for (int& i : arrR) {i = tr[i].r;}return query_kth(arrL, arrR, k - sum, mid + 1, r);}}int query_rank(vector<int>& arrL, vector<int>& arrR, int l, int r, int x) {if (x < l) {return 0;}if (x >= r) {// 目标值大于等于当前区间：返回整个区间计数int sum = 0;for (int i : arrR) {sum += tr[i].v; // 右区间总和}for (int i : arrL) {sum -= tr[i].v; // 减去左区间总和}return sum;}int mid = (l + r) >> 1;if (x <= mid) {// 目标值在左子树：所有节点向左移动for (int& i : arrL) {i = tr[i].l;}for (int& i : arrR) {i = tr[i].l;}return query_rank(arrL, arrR, l, mid, x);}else {// 目标值在右子树：先计算左子树总和int sum = 0;for (int i : arrR) {sum += tr[tr[i].l].v; // 右区间左子树和}for (int i : arrL) {sum -= tr[tr[i].l].v; // 减去左区间左子树和}for (int& i : arrL) {i = tr[i].r;}for (int& i : arrR) {i = tr[i].r;}return sum + query_rank(arrL, arrR, mid + 1, r, x);}}
};struct Node {int l, r, v;Node(): l(0), r(0), v(0) {}
};