树分治

点分治

选择一个点将无根树变为有根树,再递归处理每一棵以根节点儿子为根的子树。

例题1

[IOI2011]Race

求一条路径使得权值和为k且边的数量最小。

解法

用一个桶记录对应边权的最小边数。按照常规点分治做法处理。

边分治

例题1

[bzoj2870]最长道路tree

解法

枚举路径最小值,统计贡献。

链分治

CDQ分治

整体二分

需要满足性质:

顾名思义就是对所有询问一起二分

询问类似于第几次修改后满足条件

例题

Meteors

分块

如果每次操作复杂度为$O(1)$则复杂度为$O(n\sqrt n)$。

若单次操作复杂度带$log$可通过调整块大小使得复杂度为$O(n\sqrt{nlogn})$。

 

莫队

复杂度证明

对于左端点,在同一块内转移,一次不超过$\sqrt n$,在不同块间转移次数不超过$\sqrt n$。

对于右端点,同一类内移动次数不超过$n$,最多$\sqrt n$类。

所以总复杂度为$O(n\sqrt n)$。

强制在线莫队

选取一些关键点,预处理出关键点到任意点的答案,询问时左端点右移即可。

树分块&树上莫队

借助dfs序(括号序列)。可将一个连通分量缩成一个序列。

例题

[SPOJ]COT2

给定一棵n个颜色的树,m次查询,每次询问(u,v)路径上颜色种类。

做法2

主席树。

定义pre[i]为颜色与i相同的最近的祖先,其他同莫队及序列上数颜色。

块状链表

例题

[BZOJ3337]

维护一个原序列块状链表,同时维护一个块内有序的块状链表即可。码量较大。

keyboard_arrow_up