给定 \(a_0 ...,a_{2^\omega -1}\) ，对于 \(k \in [0,w)\) 求第 \(k\) 位为 \(1\) 的数的 \(a\) 的和。
首先可以 \(\mathcal O(2^\omega\omega)\) 计算，考虑优化
将所有数插到 01trie 中，注意到 01trie 是满的，可看作线段树的结构。
那么可以得到 \(x\) 插入的位置为 \(2^\omega +x\)
做一遍子树和，第 \(i\) 位的答案为第 \(i\) 层向右到达点的权值和。
复杂度 \(\mathcal O(2^\omega)\)
标签：数插,运算,01trie,权值,mathcal,omega From： https://www.cnblogs.com/chihik/p/16911972.html