前言

最近研究了这几个，发现它们的形式长的挺像的，所以开个坑塞在一起讲讲。

有错误可以私信指出。

更新

upd on 2024.10.10：增加线段树分治一道例题。修改了一些错误 by @wimg6_。
upd on 2024.10.15：增加了树分治部分。同时写完了点分治相关内容，开始写点分树。
upd on 2024.10.17

基础：普通分治

首先分治的思想即将一个问题划分为多个易求解的子问题，然后合并得到答案。

对于某些算贡献的题目，常见的分治可以是这样的（以 \operatorname{solve}(l,r) 为例）：

• 递归处理 \operatorname{solve}(l,mid) 和 \operatorname{solve}(mid+1,r)。为保证复杂度一般取区间中点 mid=(l+r)>>1。
• 合并答案。例如乘在一起。

好了你已经学会基础的分治了.jpg

分治的思想被广泛运用，以下会讲解分治的进阶内容和思想。

CDQ 分治

CDQ 分治的重点在于答案的合并部分。

相对于一般的分治左右两部分不相干，合并时可以直接加起来。
那如果遇到右区间的答案与左区间有关时该怎么办呢？CDQ 分治的思想则是将左区间算好的答案与右区间进行合并。
还是以 \operatorname{solve}(l,r) 为例：

• 递归处理 \operatorname{solve}(l,mid)。
• 此时将左边已经算好的区间中可能的答案贡献到右边。
• 右边算好了，可以 \operatorname{solve}(mid+1,r)。

CDQ 分治的思想被运用在多个方面。

点对统计

为了便于理解其思想，先从简单题开始讲起。如有基础可直接跳至三维偏序部分。

典中典逆序对

给你一个序列，求逆序对个数。

考虑分治的思想，对于 [l,r] 如何贡献答案呢？
假设我们分别算完了左右区间互不相关的答案，现在还差一件事：如果有两个点 i,j\ (a_i>a_j) 分别在左右区间，如何统计答案？
运用 CDQ 的思想，先枚举左区间的每一个数，将其丢到树状数组里。此时再枚举右区间的数 x，查询 (x,n] 的数的数量即可。复杂度是 O(n\log^2n) 的（假设不考虑直接的 O(n\log n) 做法）。

更进一步：发现逆序对就是在统计 i<j 且 a_i>a_j 的数对数量。这样就引出下一个问题：

二维偏序（数点）

有 n 个数，每个数有两个属性 a_i,b_i。对于每个 i 求同时满足 a_j<a_i,b_j<b_i 的 j 的数量。

你发现虽然有二维，但是这样子显然不是最优的：如果对其中一维排序，就能在不改变其他条件情况下直接满足一个条件的限制。
按 a_i 排序，此时就变成了上文所说的逆序对（或顺序对）问题。

如果增加到三维呢？

P3810 【模板】三维偏序（陌上花开）

有 n 个数，每个数有三个属性 a_i,b_i,c_i。求同时满足 a_j\le a_i,b_j\le b_i,c_j\le c_i 的数对的数量。

我会树套树！但是树套树码量常数都大，有没有什么更好的？

根据上文的启发，不难想到先按 a_i 排序，这样就少了一维的限制。那么剩下两维呢？如果按照上文再对 b 排序就好了，但是这样子排好的 a 又乱了！

此时我们回想起了 CDQ 分治，即将左区间的值贡献到右区间。左贡献右就说明 a 的限制是必然满足的，此时再对 b 排序就可以了。

怎么做呢？假如左右排好序了，不难想到使用归并排序维护左右扫到的点 i,j。此时显然应该由左侧 b 较小的贡献到右侧 b 较大的，直接使用树状数组就好了：

• 如果 b_i<b_j，归并排序要我们加入 i，由于 i 在左区间，其是能贡献到之后所有右区间的，只需要按二维偏序的方法将 c_i 加入树状数组就行了！
• 否则，j 以后的左区间由于 b 较大必然不会贡献到 j，而小于 j 的都已经在树状数组里了。直接查询 [1,c_j) 的数个数即可。

这样我们就处理完左区间对右区间的贡献了。复杂度是 O(len\log V) 的。其中由于分治 len 的和是 O(n\log n) 的。总复杂度显然为 O(n\log n\log V)。

会不会有没算到的贡献呢？由于是分治，那些不分别在左右的数对会在后续被更新。

细节上几个注意的点：

• 树状数组清空时一定不要全部扫一遍，此时单次的复杂度就不是与 len 而是与 n 相关，直接爆炸。
• 题目是小于等于，所以对于全部相同的值要粘在一起算。

这可比树套树好写多了（偷懒没归并）：

il void work(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    work(l,mid);work(mid+1,r);
    sort(v+l,v+mid+1,cmp2);sort(v+mid+1,v+r+1,cmp2);
    int j=l;
    forto(i,mid+1,r){
        while(j<=mid&&v[j].b<=v[i].b){
            arrt::add(v[j].c,v[j].cnt);j++;
        }
        v[i].ans+=arrt::qry(v[i].c);
    }
    arrt::init();
}

P3157 [CQOI2011] 动态逆序对

多次删点，每次操作后查询逆序对数量。

引入分治中重要的一个东西：时间维度。

发现前面的删除操作会干扰后面的查询，此时就不能忽略时间的影响。那我们直接把时间维也考虑进去不就行了！

如果我们按时间维排序，在时间维上分治，显然有左区间能贡献到右区间，反之则不行。

记 id_i 表示 i 原来的 id，那么按时间排序后逆序对只有当 i<j,id_i<id_j,a_i>a_j 时才会产生贡献。
此时三维偏序即可。

拓展：
CDQ 套 CDQ 可以实现四维偏序（还不会）。
更高维度数据结构（或是 CDQ 层层套娃）的 \log 越叠越多（可以认为 k 维是 O(n\log^{k-1}n) 的）且码量巨大。
所以当维度上升到一定时会选用 bitset 做法。

在线转离线

矩形加矩形求和

二维平面。支持某个矩形全部加上一个数和查询在矩形内点的权值和。

发现由于有修改，所以不好离线。如果可以离线那么就可以直接按 x 排序使用扫描线了。

如果我们把修改也一起离线下来呢？参考上题，按时间维分治。还是左区间修改贡献右区间查询。既然是求矩形的和，那么贡献可以拆开，只需考虑当前的这段。

先把左区间的所有修改丢到平面上，直接按离线做法扫描线将右边的加上答案即可。

至于其他的修改-查询关系，只需分治到左右即可。

拓展：当修改之间不独立时（如赋值）递归顺序必须满足先左然后统计答案再右。或者使用下文的其他分治方法。

整体二分

整体二分其实可以看作对可能答案的分治。

一般适用于答案是位置而不是权值和，即答案较小的情况。

P3527 [POI2011] MET-Meteors

你有长度为 n 的序列 a_i，q 次操作对区间 [l,r] 整体加上 c，对于每一个 i 求最先哪次操作后有 a_i\ge lim_i。

如果只需要求一个 i 可以怎么做？看到最先哪次操作显然能想到二分（当然先不考虑枚举的事）。

假设二分到 mid，只需要求 mid 前所有操作对 i 加上的贡献与 lim 比较就行了！于是你发现这样是 O(n\log n) 的。

能把 \log 去掉吗？显然可以！假设当前答案的可能区间是 [l,r]，那么 [1,l) 之间的操作就必定会选到。即我们在 [l,r]\to(mid,r] 时，扫描一遍先把一定能算到的 [l,mid] 的贡献加上。

但是很不幸，这题不止一个 i。你发现每次二分的过程都要把询问扫一遍，又没有更快的做法？
如果把所有询问放在一起二分呢？

此时我们发现每次 check 的复杂度没有大变化——只需要上一个神奇的树状数组维护每个点当前的 a_i 就行了，O(n)\to O(n\log n)，完全可以接受！
而且此时 check 会一次性解决所有的询问。那么把这些询问分成两类：一类是答案在 [l,mid] 的，另一类是在 (mid,r] 的。

于是你想到了分治。只需对询问进行分治即可。在分治时一定要注意的是复杂度必须只与 len=r-l+1 有关，而不能变成 O(n) 等，这样一共分治 q\log q 次就会把复杂度炸成 O(nq\log q) 的。

想到上文对于单个点二分的优化，我们只需要让对 [l,r] 分治时 [1,l) 的值已经在树状数组里就行了。这样只需扫描 [l,r] 而非 [1,r]，保证了 O(len\log n) 的复杂度。

怎么实现呢？对于 [l,mid] 显然是满足的，对于 (mid,r] 只需把 [l,mid] 加入即可。

总结一下：

• 维护一个 vector 表示在分治区间内的答案。将 [l,mid] 加入树状数组，扫一遍 vector 得出哪些在左哪些在右。
• 把 [l,mid] 删掉，处理 [l,mid] 的答案。操作完后此时树状数组里面已经有了 [1,mid]。
• 直接处理 (mid,r]。这样树状数组里就有了 [1,r] 全部了。

vector 好写，但是略慢。当时代码写的方法也更复杂一些，仅供参考。时间复杂度是 O(n\log^2 n)。

il void solve(rnt l,rnt r,vector<int> qry){
    if(qry.empty())return;
    if(l==r){
        forv(i,qry.size())ans[qry[i]]=l;
        return;
    }
    rnt mid=(l+r)>>1;

    for(rnt i=mid+1;i<=min(r,q);i++)upd[i].work(-1);
    rnt id,sum;
    vector<int> ok,no;
    forv(i,qry.size()){
        id=qry[i];sum=0;
        forv(j,e[id].size())sum+=st::qry(e[id][j]);
        if(sum>=b[id])ok.emplace_back(id);
        else no.emplace_back(id);
    }
    solve(l,mid,ok);
    for(rnt i=mid+1;i<=min(r,q);i++)upd[i].work(1);
    solve(mid+1,r,no);
}

P1527 [国家集训队] 矩阵乘法

简单题。

先讲讲区间第 k 小数怎么做。整体二分答案，把小于等于 mid 的设为 1，否则为 0，则当区间内 1 数量不小于一半时取到答案。同样的，按照上文，只处理 [l,r] 间的值，其它的已经在之前维护好了。复杂度应该是 O(n\log^2 n) 的。

那到矩形上也是一样的，用二维树状数组维护，复杂度 O((n^2+q)\log^3 n)。

决策单调性优化

决策单调性优化主要用于优化 dp。

因为不是重点，不会详细讲解证明过程。主要讲较为简单的 dp，形式为 f_i=\max/\min(f_j+w(j,i))。

决策单调性 / 四边形不等式

先解决 f_i=\min w(j,i) 的形式。

如果 i 的最优决策点为 best_i，即 i 从 best_i 转移过来，则决策单调性可以理解为 \forall i<j,best_i\le best_j。感性理解一下，最优的决策点和当前的 dp 位置类似双指针的移动，即不会倒退。

四边形不等式为 \forall i\le j\le k\le l,w(i,k)+w(j,l)\le w(i,l)+w(j,k)。即交叉优于包含。同理在 f_i=\max w(j,i) 时上面的 \le 要变成 \ge。

满足四边形不等式即有决策单调性。

简易证法：
反证，如果 a<b 但 best_a>best_b 即 best_b<best_a\le a<b。
则 w(best_a,a)<w(best_b,a),w(best_b,b)<w(best_a,b)。
二者相加，有 w(best_a,a)+w(best_b,b)<w(best_b,a)+w(best_a,b)，你发现不满足交叉优于包含。于是爆了。

同时你还发现对于奇奇怪怪的 f_i=\min(g_j+w(j,i)) 只要 w 满足四边形不等式整体也是有决策单调性的。

然后有了这个终于可以切入正题了。

分治法

分治法主要用于 f_i=\min(g_j+w(j,i)) 中 g_j 与 f_j 无关的情况。

P3515 [POI2011] Lightning Conductor

给定一个长度为 n 的序列 \{a_n\}，对于每个 i\in [1,n] ，求出一个最小的非负整数 p ，使得 \forall j\in[1,n]，都有 a_j\le a_i+p-\sqrt{|i-j|}

正着反着做两遍即可钦定 j<i，然后把根号的绝对值去掉。

考虑怎么找出 \max(a_j+\sqrt{i-j})。感觉上这个满足四边形不等式（许多类似题都可以打表验证），于是直接做。

其思想类似于整体二分，由于有决策单调性，一段的答案是连续的，记 \operatorname{solve}(l,r,bg,ed) 表示处理 [l,r] 的 dp 值，且答案范围是 [bg,ed]。
既然答案连续，我们只需要找出分界点 mid 的答案 f_{mid}，则所有小于 mid 的点答案均小于等于 f_{mid}，大于同理。
调用 \operatorname{solve}(l,mid-1,bg,f_{mid}) 和 \operatorname{solve}(mid+1,r,f_{mid},ed) 即可。

简单易懂的代码：

il void work(int l,int r,int bg,int ed){
    if(l>r)return;
    int mid=(l+r)>>1,best=0;
    double res=0;
    forto(i,bg,min(ed,mid)){
        if(w(i,mid)>res)res=w(i,mid),best=i;
    }
    ans[mid]=max(ans[mid],res);
    work(l,mid-1,bg,best);
    work(mid+1,r,best,ed);
}

拓展：

与整体二分相比，可以发现的是由于决策单调性的性质，答案是连续的，而无需整体二分记 vector 表示当前答案集合。
同时决策单调性分治只需考虑 mid 的答案，推出前后两部分的答案区间。而整体二分则要对当中每一个询问都做一次查询来判断分在哪里。

对于 f_i=\min(f_j+w(j,i)) 等情况，分治会涉及到之前的答案所以无法使用，此时需要使用二分队列，篇幅限制就不展开了。

线段树分治

前置芝士：可撤销并查集

就是可以撤销的并查集，只需要在更新同时维护一个栈代表将哪两个点连在一起即可。

由于需要撤销所以不能使用路径压缩。代码：

namespace DSU{
    int fa[N],siz[N];
    vector<pii>op;
    il void init(int n){
        forto(i,1,n)fa[i]=i,siz[i]=1;
    }
    il int find(int x){
        return (x==fa[x])?x:find(fa[x]);
    }
    il void merge(int x,int y){
        x=find(x),y=find(y);
        if(siz[x]<siz[y])swap(x,y);
        fa[y]=x,siz[x]+=siz[y];op.eb(mp(x,y));
    }
    il void pop_back(){
        if(op.empty())return;
        int x=op.back().first,y=op.back().second;op.pop_back();
        siz[x]-=siz[y],fa[y]=y;
    }
}

线段树分治与图

P5787 二分图 /【模板】线段树分治

一张 n 个点的图，有 m 条无向边会分别在 [l_i,r_i] 时刻存在，每个时刻判断是否是一张二分图。

先考虑对于一个确定的图如何判断是否为二分图。

这里提一下扩展域并查集，把点 i 拆成两个节点 i,i+n，则每条边必须连接两个不同集合中的点，即 x\leftrightarrow y+n,x+n\leftrightarrow y。每次 check 时如果这个点拆出的两个新点被并到一起去了就不是二分图。

并查集加边是容易的，即对于某时刻加入当前插入的边。但是删除较为困难（区分撤销，撤销指的是上一次操作取消，删除是任意某个操作）。

我们能否通过某种方式把删除转化成撤销呢？

发现 i 在 [l_i,r_i] 存在是可以拆分成能并起来等于原来的两段。如果需要保证较优的复杂度，最好将其拆分成 \log 段。

此时线段树分治登场。线段树是按时间建立的。
像区间修改一样把每个边存在的时间用 vector 存到每个节点上。
然后就是最重要的操作：最后统计答案时，对于某个节点 x，它的区间起始点均相同，且能覆盖到 x 的两个儿子。此时用可撤销并查集先加入 x 上存在的边，再递归左右儿子，同时返回时只需撤销刚刚加入的边即可。

这样的复杂度就是分治的 O(n\log n) 了（不算并查集）。

代码是好久以前写的，没有格式化，可以先看下一题代码。

P4219 [BJOI2014] 大融合

动态加边和查询经过某条边的路径数量。

首先加入加边时查询贡献，显然有答案等于 siz_x\times siz_y（此时 x,y 未联通）。

这启发我们使用并查集维护节点 siz。加边就可以看作边从 t_i 开始一直存在到结束。

直接按上题做法上线段树分治即可维护某时刻的森林。

但是怎么查询呢？
好像只有在边连接的 x,y 断开时才能查询，这启发我们把区间 [st,ed] 拆成 [st,t) 和 [t,ed]，即在查询前把边断掉然后再连起来看贡献。
这样就做完了。

由这两题可见，线段树分治可以用来维护容易插入而删除困难的数据结构。

线段树的码量还是比之前几个要大的。代码：

int n,q;
ll ans[N];
namespace SegT{
    struct Qry{
        int x,y,initid;
    };
    vector<Qry>qry[N];
    vector<pii>op[N*5];
    int bg,ed;pii dat;
    il void _insert(int x,int l,int r){
        if(bg<=l&&r<=ed){op[x].eb(dat);return;}
        int mid=(l+r)>>1;
        if(bg<=mid)_insert(x<<1,l,mid);
        if(mid<ed)_insert(x<<1|1,mid+1,r);
    }
    il void insert(int _bg,int _ed,pii _dat){
        if(_bg>_ed)return;
        bg=_bg,ed=_ed,dat=_dat;_insert(1,1,q);
    }
    il void solve(int x,int l,int r){
        for(pii p:op[x])DSU::merge(p.first,p.second);
        if(l==r){
            for(Qry q:qry[l])ans[q.initid]=1ll*DSU::getsiz(q.x)*DSU::getsiz(q.y);
        }else{
            int mid=(l+r)>>1;
            solve(x<<1,l,mid);solve(x<<1|1,mid+1,r);
        }
        forv(i,op[x].size())DSU::pop_back();
    }
}

注：下面题目原还需要图上维护线性基的技巧，与主题关系较小略过不讲，例题经过笔者转化。如有需要了解的可以看P4151 [WC2011] 最大XOR和路径。

P3733 [HAOI2017] 八纵八横 二次转化版

有一个集合 S，多次插入和删除元素。求每个操作后集合内选择任意数字能获得的最大异或和。每个元素 x<2^m\ (m\le1000)。插入和删除的操作次数较小。

首先对于一个确定的集合，使用线性基即可求得最大异或和。注意到 m 较大需要使用 bitset。

我们注意到普通的线性基是难以删除和撤销的，这启发我们使用整体二分。

按照上题的套路，将每个元素存在的时间段找出来，然后将区间插入线段树。

但是你发现维护时出了困难：线性基没办法撤销，如何回溯呢？
直接暴力记下线段树上每个点一开始的线性基，回溯时赋值回去即可。
但是线段树有 n\log n 个节点，而线性基需要的空间是 O(\frac{m^2}{w}) 的，这就爆炸了！
可是你发现赋值完后记的线性基就没用了，而由于线段树最高 \log n 层，则最多递归 \log n 层，每层只需要记一个线性基就行了。

时间复杂度 O(\frac{m^2n\log n}{w})，空间复杂度是 O(\frac{m^2\log n}{w}) 的。

LB 是线性基，bst 是长度为 m 的 bitset。

namespace SegT{
    vector<bst>upd[N*5];
    bst ans[N];
    int bg,ed;bst add;
    il void insert(int x,int l,int r){
        if(bg<=l&&r<=ed){upd[x].eb(add);return;}
        int mid=(l+r)>>1;
        if(bg<=mid)insert(x<<1,l,mid);
        if(mid<ed)insert(x<<1|1,mid+1,r);
    }
    il void insert(int _bg,int _ed,bst _add){
        if(_bg>_ed)return;
        bg=_bg,ed=_ed,add=_add;
        insert(1,1,q);
    }

    il void solve(int x,int l,int r){
        if(l>r)return;
        LB tmp;tmp.init(base);
        forv(i,upd[x].size())base.insert(upd[x][i]);
        if(l==r){
            ans[l]=base.getmax();
        }else{
            int mid=(l+r)>>1;
            solve(x<<1,l,mid);solve(x<<1|1,mid+1,r);
        }
        base.init(tmp);
    }
}

总结

适用范围：

• CDQ 分治：点对统计、在线转离线。
• 整体二分：使二分 check 复用、优化二分。
• 决策单调性分治：解决部分满足决策单调性的 dp。
• 线段树分治：维护不便于删除的数据结构。

树分治

点分治

点分治常用于解决与点对或路径有关的问题。

P3806 【模板】点分治 1

给定一棵有 n 个点的树，询问树上距离为 k 的点对是否存在。

转化为求树上是否有长度为 k 的路径。

首先有一个最基础的分治思想，把大问题转化为小的互不相干子问题。
对于当前子树根节点 x 将可能的路径分为两部分：

• 经过 x 的。
• 未经过 x 的。

发现未经过 x 的路径一定分别分散在几个子树内，递归求解它们就可以了。

考虑怎么统计经过 x 的路径。
经过 x 的路径则可以转化为一个子树的某一个节点开始经过 x 到另一个子树内。
依次枚举某棵子树内的每一个点到 x 的距离为 dep_i，只需要找出是否存在 dep_j+dep_i=k 且 j 在其它子树内。
这是好做的，一个思路是直接 map 查询枚举到 i 这棵子树之前是否有 dep_j=k-dep_i 即可。

解决了分治的问题，但是我们发现一件事情：如果分治从一条链的一个端点开始，每次扫描都是 O(n) 的，这样就退化成了 O(n^2)。有没有什么可以优化的方法？

我们发现对于一个子树，选择什么样的 x 对答案是无所谓的，而算法的复杂度又与 x 的选择高度相关。
连想到树的重心，重心具有很优秀的性质。那我们只需要每次找出重心当作子树的 x，就能优化算法的复杂度。此时递归深度最多为 O(\log n) 层，每一层都只会扫一遍的 n，复杂度即为 O(n\log n)。
推荐一篇讲解复杂度的文章。

可以看到，点分治可以通过重构树的结构统计路径信息。

维护点对进阶。

P4178 Tree

给定一棵有 n 个点的树，询问树上距离小于等于 k 的点对数量。

我们发现这一题和上一题很像。但是变成了查询距离小于的数量。

还是求经过 x 的路径数量，那么两个端点需要满足 dep_i+dep_j\le k，即 dep_j\le k-dep_i。发现其具有单调性，那么想到双指针。
在双指针扫描的时候同时还有另一个细节：i 和 j 不能属于同一个子树。否则 i 到 j 的路径就无法经过 x。

实现时需要注意每次分治的复杂度与 siz_x 有关而非 x。原因与普通分治是一样的。

int n,k,rsiz[N];
ll ans=0;
vector<pii>e[N];
il void init(int x,int fa){
    rsiz[x]=1;
    for(pii p:e[x]){
        int y=p.first;if(y==fa)continue;
        init(y,x);
        rsiz[x]+=rsiz[y];
    }
}
int siz[N],treesiz,minx,rt;
bool vis[N];
il void findroot(int x,int fa){
    siz[x]=1;int maxs=0;
    for(pii p:e[x]){
        int y=p.first;if(y==fa||vis[y])continue;
        findroot(y,x);
        siz[x]+=siz[y],maxs=max(maxs,siz[y]);
    }
    maxs=max(maxs,treesiz-siz[x]);
    if(maxs<minx)minx=maxs,rt=x;
}
il int find(int x){
    minx=0x3f3f3f3f,rt=0,treesiz=rsiz[x];
    findroot(x,0);return rt;
}
int clr[N],son[N],tot=0,dep[N],cnt[N];
il void getch(int x,int fa,int d,int rt){
    son[++tot]=x,clr[x]=rt,cnt[rt]++,dep[x]=d;
    for(pii p:e[x]){
        int y=p.first;if(vis[y]||y==fa)continue;
        getch(y,x,d+p.second,rt);
    }
}
il void dfs(int x){
    // printf("%d\n",x);
    vis[x]=1,tot=0;
    for(pii p:e[x]){
        int y=p.first;if(!vis[y])getch(y,x,p.second,y);
    }
    sort(son+1,son+tot+1,[](int x,int y){return dep[x]<dep[y];});
    forto(i,1,tot)ans+=dep[son[i]]<=k;
    for(int i=1,j=tot;i<=tot;i++){
        cnt[clr[son[i]]]--;
        while(j>0&&dep[son[j]]+dep[son[i]]>k)cnt[clr[son[j]]]--,j--;
        if(j<=i)break;
        ans+=j-i-cnt[clr[son[i]]];
    }
    forto(i,1,tot)cnt[clr[son[i]]]=0;

    for(pii p:e[x]){
        int y=p.first;if(vis[y])continue;
        dfs(find(y));
    }
}

点分树

我们发现，点分治中每次找子树重心的性质是非常优秀的，但是通过上面两道例题，我们发现点分治只能处理一次整体的询问。对于多次询问，是否有类似的方法呢？

由于原树和点分树极易混淆，下文统一记 \operatorname{operator}(\cdots) 表示与原树有关，记 \operatorname{operator}^{\prime}(\cdots) 表示与点分树有关。

P6329 【模板】点分树 | 震波

给定一棵树，初始有点权，有多次询问和修改：

• 将 x 点权变为 v。
• 查询树上与点 x 距离在 k 内的点的点权和。

点分树其实就是将点分治过程中的父节点与子树的重心连边，可以认为是对树的高度进行了压缩，其深度是 \log n 的。

父节点与子树的重心连边的过程显然会打乱原树的父子顺序，也就是说，点分树只能处理与父子顺序关系不大的问题，例如距离。

记 x,y 在原树上的距离为 \operatorname{dis}(x,y)。
首先有一个结论，\operatorname{dis}(x,y)=\operatorname{dis}(x,\operatorname{lca}^{\prime}(x,y))+\operatorname{dis}(\operatorname{lca}^{\prime}(x,y),y)。即 \operatorname{lca}^{\prime}(x,y) 一定在 x 到 y 的路径上。
换言之，x 到 y 上任意点都可以计算 x,y 的贡献，照应了上文点分树与父子顺序关系不大的要求。

先考虑单次查询。由于点分树树高为 \log n，我们可以考虑直接暴力跳 x 的父亲 fa^{\prime}_x（记为 t^{\prime}），还是按照点分治的思路，尝试每次统计 t^{\prime} 的贡献。
考虑拆开式子：

\operatorname{dis}(x,y)=\operatorname{dis}(x,t^{\prime})+\operatorname{dis}(t^{\prime},y)\le k $$\operatorname{dis}(t^{\prime},y)\le k-\operatorname{dis}(x,t^{\prime})$$ 和上文的点分治一样，**$x,y$ 必须在 $t^{\prime}$ 的两棵不同子树内**才能保证路径经过 $t^{\prime}$。 那么对于单次询问只需和点分治的套路一样，枚举 $t^{\prime}$ 统计答案。这是简单的，需要注意的是要扣掉 $x,y$ 在同一子树内的情况（记这颗 $x$ 所在的子树为 $son^{\prime}$）。 记 $\operatorname{cnt}_1(x^{\prime},k)$ 表示在**点分树上 $x^{\prime}$ 的子树中**到点 $x^{\prime}$ 距离小于等于 $k$ 的点的数量，$\operatorname{cnt}_2(x^{\prime},k)$ 表示在**点分树上 $fa^{\prime}_{x^{\prime}}$ 的子树中**到点 $fa^{\prime}_{x^{\prime}}$ 距离小于等于 $k$ 的点的数量。则有： $$ans=\operatorname{cnt}_1(t^{\prime},k)-\operatorname{cnt}_2(son^{\prime},k)$$ 解释一下为什么要设两个 $\operatorname{cnt}$：在**点分树**上为父子关系的两个节点，原树上距离可能差距很大。我们不能简单地将其变为 $\operatorname{cnt}_1(son^{\prime},k-1)$，因为我们不知道 $t^{\prime}$ 到 $son^{\prime}$ 的距离是多少。 那么暴力跳父亲，暴力找子树内满足该距离（是原树上距离，可以用树剖求）的节点数量，减掉不满足的即可。 对于多组询问，~~注意到~~每次只会修改一个点或查询一段连续区间，想到对于每一个 $\operatorname{cnt}_{1/2}(t^{\prime},\cdots)$ 维护一个**树状数组**。即区间查询小于距离的点权和，单点修改某个距离上的点权值。 一个细节是，树状数组需要使用 vector，因为直接使用数组会导致 MLE。一共 $n$ 个点，由于每个子树深度不深，每个点内不需要开太大的空间，总共只需 $O(n\log n)$ 即可。注意原下标是 $0$ 开始的，需要加上 $1$。 ```cpp namespace AT{ vector<int>c[N][2]; il void resiz(int id,int siz){ c[id][0].resize(siz),c[id][1].resize(siz); } il void add(int id,int op,int p,int v){ for(p++;p<c[id][op].size();p+=(p&-p))c[id][op][p]+=v; } il int qry(int id,int op,int p){ int a=0;for(p=min(p+1,(int)c[id][op].size()-1);p;p-=(p&-p))a+=c[id][op][p];return a; } } ``` 太长了。[完整代码](https://www.luogu.com.cn/paste/ml8i12z1) --- > #### [P2056 [ZJOI2007] 捉迷藏](https://www.luogu.com.cn/problem/P2056) > 给你一棵点权为 $0$ 或 $1$ 的树，初始点权均为 $1$。有若干次反转点权操作，求树上最远的两个点权为 $1$ 的点的距离。 我们发现，这题与上一题的区别在与询问是全局的，而非某个点。 还是考虑如何维护 $t^{\prime}$ 的答案。和上一题类似地，我们在 $t^{\prime}$ 上尝试维护一个数据结构，在更新的同时也更新整体答案。 发现我们要求最长长度，可以想到使用**大根堆**。发现一条路径可以看作**从一个子树最深的点走到另一个子树最深的点**，如果我们记 $\operatorname{sonh}^{\prime}(x)$ 表示 $x$ 的每个子树的最大深度组成的集合，使用大根堆找出最大和次大值即可。 为了维护每个子树的最大深度，我们还需要记 $\operatorname{mxdep}^{\prime}(y)$ 表示 $y$ **点分树上的子树内**到 $fa^{\prime}_y$ 距离最远的点的集合，同样使用大根堆维护。 为什么不能直接维护到自己的距离的原因和上一题相同：点分树破坏了原树的结构，可能 $x$ 与 $fa^{\prime}_x$ 并不相邻。 由于有修改操作，大根堆还需支持删除任意元素，我们可以再记一个 erase 的堆代表需要删除的点，如果其和原来的堆堆顶相同，就将其二者一起弹出。代码： ```cpp struct Heap{ priority_queue<int>q,ers; il void push(int x){if(x>=0)q.push(x);} il void erase(int x){if(x>=0)ers.push(x);} il int top(){ while(!ers.empty()&&q.top()==ers.top())q.pop(),ers.pop(); return q.empty()?-1:q.top(); } il void pop(){ while(!ers.empty()&&q.top()==ers.top())q.pop(),ers.pop(); q.pop(); } il int top2(){ int tp=top(),ans;if(tp==-1)return -1; pop(),ans=top(),push(tp); return ans; } il int get(){ int c=top2(); return (c==-1)?-1:(top()+top2()); } }ans,sonh[N],mxdep[N]; ``` 由于我们需要整体的答案，所以还需再记一个 $\operatorname{ans}^{\prime}$ 表示整体的答案，即**所有 $\operatorname{sonh}^{\prime}(x)$ 最大值和次大值的和**组成的集合。 那么如何更新贡献呢？ 首先将 $\operatorname{sonh}^{\prime}(x)$ 的贡献移出 $\operatorname{ans}^{\prime}$，将 $\operatorname{mxdep}^{\prime}(y)$ 的贡献移出 $\operatorname{sonh}^{\prime}(x)$。 此时就可以随意更新 $\operatorname{mxdep}^{\prime}(y)$ 了。更新完按顺序加回来即可。 部分代码，树剖在 `G::` 里面，建树省略了。 ```cpp bool state[N]; int cnt=0; il void upd(int x){ state[x]=!state[x],cnt+=state[x]?1:-1; ans.erase(sonh[x].get()); if(state[x])sonh[x].push(0); else sonh[x].erase(0); ans.push(sonh[x].get()); for(int i=x;fa[i];i=fa[i]){ ans.erase(sonh[fa[i]].get()); sonh[fa[i]].erase(mxdep[i].top()); if(state[x])mxdep[i].push(G::dis(fa[i],x)); else mxdep[i].erase(G::dis(fa[i],x)); sonh[fa[i]].push(mxdep[i].top()); ans.push(sonh[fa[i]].get()); } } il int qry(){ if(cnt==0)return -1; else if(cnt==1)return 0; else return ans.top(); } ``` 暂完结。