二维数点

有时会遇到 \(\Theta(n)\) 次修改，\(\Theta(n \log n)\) 次询问的二维数点问题。

可以尝试模改线段树，将其从二叉树变成 \(\Theta(\log n)\) 叉树，一共 \(\Theta\left(\frac{\log n}{\log \log n}\right)\) 层。

对每个非叶子节点的 \(\Theta(\log n)\) 个儿子维护其前缀和，单点修改复杂度 \(\Theta\left(\frac{\log^2 n}{\log \log n}\right)\)，区间查询复杂度 \(\Theta\left(\frac{\log n}{\log \log n}\right)\)。

得到总复杂度 \(\Theta\left(\frac{n \log^2 n}{\log \log n}\right)\)。

\(\Theta(n \log n)\) 次修改，\(\Theta(n)\) 次询问的二维数点问题也是一样的。

只是对每个非叶子节点的 \(\Theta(\log n)\) 个儿子直接维护一个数组，区间和暴力求，单点修改复杂度 \(\Theta\left(\frac{\log n}{\log \log n}\right)\)，区间查询复杂度 \(\Theta\left(\frac{\log^2 n}{\log \log n}\right)\)，总复杂度 \(\Theta\left(\frac{n \log^2 n}{\log \log n}\right)\)。

但是线段树可能常数比较大，跑不过直接用树状数组 \(\Theta(n \log^2 n)\) 做？

考虑能否对树状数组也像上面一样模改。