各种遍历算法
通过叶子统计树上结点数
对于一颗有根树，如果所有非叶子结点都至少有两个孩子（等价的不存在度数为$2$的结点），那么我们就可以用叶子数来约束整个树的大小，这样的树我们称其为无杆树。记$n$表示叶子数，$m$表示非叶子数，实际上可以发现$m\leq n$，因此总的树上结点数不超过$2n$。
证明非常简单，我们可以不断选择最深的一个叶子，将其父亲下的所有叶子全部删除。可以发现这样一次操作，至少会减少两个叶子，并出现一个新的叶子，因此总的叶子数至少减少了$1$，且重要的是操作后得到的新树依旧是无杆树。可以发现不断执行上面操作，直到只剩下一个根结点，我们总共最多执行$n$次操作，但是将$m$个非叶结点都转换成了叶子结点，因此有$m\leq n$成立。但是如果我们将根也视作一个叶子的话，可以发现有$m<n$成立。
上面这个技术在证明树形递归（无环）算法时间复杂度的时候非常有用。考虑一个经典的递归枚举子集算法：
void gen(int[] bits, int i, int sum){
if(i == -1){
//组合已经生成完毕，做一些操作
return;
}
gen(bits, i - 1, sum);
bits[i] = 1;
gen(bits, i - 1, sum + 1);
bits[i] = 0;
}
将每次调用视作树上的一个结点，我们发现时间复杂度恰好是$O(n+m)$。这里可以发现形成的树是无杆树，而叶子总数仅有$O(2^s)$个，其中$s$是全集的大小。因此总的时间复杂度为$O(2^s)$。由于递归遍历的时候可以维护选中的子集的摘要信息，因此实际上比一般暴力循环的$O(s2^s)$的时间复杂度会好上很多。
再考虑一个经典的递归枚举置换算法：
void gen(int[] perm, int i, boolean[] used) {
if(i == -1){
//排列已经生成，做些操作
return;
}
for(int j = 0; j < used.length; j++){
if(used[j]){
continue;
}
used[j] = true;
perm[i] = j;
gen(perm, i - 1, used);
used[j] = false;
}
}
设$p$为置换的长度。依旧我们将每次调用视作树上的一个结点，可以发现深度为$p$和$p-1$的调用次数都是$p!$，而深度小于等于$p-1$的部分是形成了一颗无杆树。因此树上结点总数为$O(p!)$。而每个结点（每次函数调用）消耗的时间复杂度为$O(p)$，因此总的时间复杂度为$O((p+1)!)$。
置换遍历
要遍历所有大小为$n$的置换，我们一般有递归和迭代两种方式。
递归方式可以用于处理全排列，时间复杂度为$O(n\cdot n!)$。好处是可以计算的时候附带处理一些约束条件，以及计算一些汇总信息。递归方式适用于生成大量的排列的情况，而它计算单个排列（比如计算某个排列的后继）的最坏时间复杂度为$O(n^2)$。这时候我们可以使用迭代的方式来优化。
迭代算法分成两类，计算某个置换的后继和前驱。我们先考虑后继，前驱版本可以逆向思维得到。
对于$P$，如何找到比$P$大且在这些置换中最小的置换呢$T$。我们应该保证$P$和$T$的公共前缀尽量长。因此我们要选择一个最短的后缀，通过调整后缀得到一个更大的置换。
很显然后缀是倒序的时候，我们不可能通过调整它得到更大的一个置换，考虑$i$为最大的下标，且满足$P_i<P_{i+1}$。我们先对$P_{i+1},\ldots,P_n$进行排序（考虑到它们是倒序的，因此只要翻转即可）。之后我们将$P_i$和排序完的$P_{i+1},\ldots,P_n$中最小的但是比$P_i$大的数交换，就可以得到后继了。
注意迭代算法是支持排列中出现相同的元素的。它计算单个排列的最坏时间复杂度为$O(n)$。但是当保证置换中不存在相同的值的情况下，我们可以得出更加好的平均时间复杂度，下面我们进行计算。
很显然单次操作的时间复杂度取决于具体翻转了多少个元素。可以发现如果我们当前操作翻转了最后$t$个元素，那么下一次翻转$t$或更多元素，必须在$t!$轮之后。即如果我们要找的是第$k$大的排列，那么这一轮中会翻转的元素等价于找到最大的一个$i$，满足$i!\mid k$，这一轮会翻转$i$个元素，记$i=f(k)$。
现在考虑$k$是均匀随机给定的，那么$\mathrm{Pr}(f(k)=i)=\frac{1}{i!}-\frac{1}{(i+1)!}=\frac{i}{(i+1)!}$。那么单次翻转的期望费用可以写作$E[\sum_{i=1}^n (i+1)x_i]$，其中$x_i$表示当前轮是否翻转$i$个元素。答案为$\sum_{i=1}^n (i+1)\mathrm{Pr}(f(k)=i)=\sum_{i=0}^{n-1}\frac{1}{i!}\leq e$。因此我们可以认为一次操作的平均时间复杂度为$O(e)$。
迭代算法中前驱和后继的计算逻辑相似，都是翻转尾部，以及一次交换操作。所以可以得出相同的时间复杂度，这里不赘述。
k大子集遍历
所谓的k大子集是正好包含k个元素的子集。
k大子集遍历的算法有不少。最简单的方式就是使用一个包含k个1的置换，并使用置换遍历算法来枚举所有的，但是时间复杂度不太清楚。
还有一个叫做Gosper's Hack的算法。它的代码如下：
// find next k-combination
bool next_combination(unsigned long& x) // assume x has form x'01^a10^b in binary
{
unsigned long u = x & -x; // extract rightmost bit 1; u = 0'00^a10^b
unsigned long v = u + x; // set last non-trailing bit 0, and clear to the right; v=x'10^a00^b
if (v==0) // then overflow in v, or x==0
return false; // signal that next k-combination cannot be represented
x = v +(((v^x)/u)>>2); // v^x = 0'11^a10^b, (v^x)/u = 0'0^b1^{a+2}, and x ← x'100^b1^a
return true; // successful completion
}
上面的代码来自wiki。
很显然它是$O(1)$的，原理我也没去了解。
但是这个算法只能处理形如$S=2^n-1$这样的集合的子集。之前没有注意，一直以为可以处理任意形式的子集，结果某次Topcoder比赛上用了这个板子，最终成功FST了。
下面讲一下具体如果找任意集合的所有k大子集。原本是希望通过改造Gosper's Hack算法来实现，但是里面用到下整除的黑魔法，搞不太定。下面讲一下我的做法。
我们先考虑$S=2^n-1$的形式，我们要从小到大枚举$S$的所有的k大子集。我们维护最低位1所在连通块的信息（如果两个1相邻，我们认为它们在一个连通块中），假设它们的范围从第l位开始，到第r位结束。
现在我们考虑要找到下一个k大子集。怎么找，根据取下一个置换的算法，实际上我们需要将第$r+1$位设置为$1$，将$l$到$r$位设置为$0$，之后将$0$到$r-1-l$位都设置为$1$。
由于只涉及一些二进制操作，实际上我们可以$O(1)$执行上面所有的操作。难点在于要维护$l$和$r$。如果$r-1\geq l$，那么上面的流程后我们能很容易维护新的$l',r'$。否则，新的$l'=r+1$，$r'$的话我们可以暴力从$l'$开始查找，直到找到第一个$0$位置。
上面涉及到暴力查找$r'$的过程是摊还$O(1)$的，可以认为我们每次我们右移一个$1$的时候（对应将$r$位置$0$,将$r+1$位置$1$），我们实际支付了两笔费用，一笔是移动的费用，一笔是支付后面用于扫描的费用。很显然一个被扫描的$1$之前一定被移动过，因此扫描的时候可以用预付的费用来支付。摊还时间复杂度为$O(1)$。
因此总的每次调用的时间复杂度均为$O(1)$。
现在你可能会问，这个算法和Gosper's Hack解决的问题有什么不同吗？
解决的问题是一样的，但是这个新的算法很容易扩展。现在考虑任意的集合$S$，我们先将其中所有$1$出现的位置进行排序，记第$i$个$1$出现的位置为$p_i$，并假设其中出现了$n$个$1$。之后我们维护另外一个集合$T=2^n-1$。之后我们用上面提到的算法遍历$T$的所有k大子集$t$，同时我们为$S$维护对应的k大子集$s$。这样对所有$t$的操作，我们可以同步修改$s$，比如设置$t$的第$i$位，等价于设置$s$的$p_i$位，而反转$t$的$l,r$区间，等价于我们让$s$先异或上$2^{p_1}+\ldots+2^{p_r}$，之后再异或上$2^{p_1}+\ldots+2^{p_{l-1}}$，这部分可以通过前缀和计算。
因此我们得到了一个预处理$O(\log_2 S)$，且$O(1)$计算下一个k大集合的算法。
实际上这个算法非常容易扩展，考虑我们需要同时计算得到的k大集合的一个摘要（比如给集合每个元素赋予一个权重，要算子集的权重和）。一般的做法会每次计算下一个k大集合的时候时间复杂度提高到$O(k)$，但是实际上我们可以同步维护当前的摘要信息，只要它支持批量增加元素和批量删除元素。这样时间复杂度依旧不变，是$O(1)$。