线性基kth在线复杂度能否做到亚 log 方?
  • 板块学术版
  • 楼主robinyqc
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/9/11 15:38
  • 上次更新2023/11/2 21:28:56
查看原帖
线性基kth在线复杂度能否做到亚 log 方?
338632
robinyqc楼主2023/9/11 15:38

我们要在线维护以下几个操作:

  1. 插入一个数。
  2. 查询异或第 kk 小值。

显然可以的是每次查询的时候 log⁡2\log^2 rebuild 一下。这样复杂度是 O(nlog⁡2V)O(n\log^2V) 的。

但是是否可以做到 O(nlog⁡Vlog⁡log⁡V)O(n\log V\log \log V) 甚至更小?我感觉可以,但又感觉有点不行。

2023/9/11 15:38
加载中...