@[wzhm54nr](/user/1071328) 复杂性是什么。
时间复杂度 $O(n \log n)$
by QWQ_123 @ 2024-03-09 17:06:01
@[wzhm54nr](/user/1071328) 因为 $lowbit()$ 每次会删除一个二进制，最多 $\log n$ 位，所以单次 $\log n$
by QWQ_123 @ 2024-03-09 17:06:45
对啊，可是它跑过了n=1e7
@[QWQ_123](/user/740328)
by wzhm54nr @ 2024-03-09 17:07:43
@[wzhm54nr](/user/1071328) 因为跑不满罢，我树状数组 $\log^2$ 都能跑过 $10^6$。
by QWQ_123 @ 2024-03-09 17:14:30
@[wzhm54nr](/user/1071328) 为啥不能跑过
by lonely_seele @ 2024-03-09 17:14:48
@[wzhm54nr](/user/1071328) 因为满打满算 $\log n$ 位，但是很多时候远远不到。
by QWQ_123 @ 2024-03-09 17:15:03
@[lonely_seele](/user/226449) 理论不能，但是常熟小可以过
by QWQ_123 @ 2024-03-09 17:15:20
@[lonely_seele](/user/226449) 或者说 $n \le 10^7$，可能标程就是 $O(n)$ 的罢（
by QWQ_123 @ 2024-03-09 17:15:50
谢谢奆佬
@[QWQ_123](/user/740328)
@[lonely_seele](/user/226449)
by wzhm54nr @ 2024-03-09 17:20:21
@[QWQ_123](/user/740328) 为啥理论不能 粗算下 ln1e7 也就 16 啊
by lonely_seele @ 2024-03-09 17:26:56