saintxk的博客

博客

2022-06-10 18:38:58 By saintxk

rt。

每次修改直线 $x\leq p$ 左侧的点，查询 $y\leq q$ 的点。（比如维护权值和）

有可以做到比二维线段树优的复杂度的做法吗？qwq（期望 poly log，kdt 先不考虑 qwq）

就算时间复杂度相同，空间复杂度低于 $\log^2$ 也可以。 /kel

Cat_shao

二维线段树时间复杂度不是 $O(n \log^2 n)$ 的吧。考虑询问一个很扁（长接近 $n$ ，宽很小），需要遍历很多叶子结点，大概有 $O(n)$ 个。

saintxk

@Cat_shao 我这个是散点集修改查询的意思

saintxk

比如给一个排列 $p_i$，每次前缀加，查询 $p_i \le q$ 的位置的数值之和这种

saintxk

@Cat_shao 没看懂你画的啥。。话说为什么踩我的博客

142857cs

@saintxk kdt在这个问题上已经是足够优秀的做法二维线段树是假做法

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。