有时会遇到 \(\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)\) 做?
考虑能否对树状数组也像上面一样模改。
标签:right,frac,log,复杂度,数点,二维,Theta,left From: https://www.cnblogs.com/FidoPuppy/p/17962442