求助:请问树状数组套离散化后动态开点线段树空间应该如何计算?
查看原帖
求助:请问树状数组套离散化后动态开点线段树空间应该如何计算?
26525
poplpr楼主2021/3/22 15:41

大佬萌,这道题空间大小应该是 O((n+m)log2(n+m))O((n+m) \log^2 (n+m)) 的吧,那么把 n+m=100,000n+m = 100,000 带入计算大约是 100000172=28900000=2.89107100000 \cdot 17^2 = 28900000 = 2.89 \cdot 10^7

但是蒟蒻看题解都差不多只开了 41064 \cdot 10^6 数量级的空间,如这篇题解 https://www.luogu.com.cn/blog/bfqaq/qian-tan-shu-zhuang-shuo-zu-quan-zhi-shu

请问大佬萌,这道题空间到底是怎么计算的呢?

2021/3/22 15:41
加载中...