脚本宝典收集整理的这篇文章主要介绍了题解【UVA12983 The Battle of Chibi】，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

这题已经有多篇几乎一样的题解了，讲得很明白，可没讲清楚为什么想到用树状数组代替别的数据结构，参考蓝书所写。

正常来说，执行插入，查询前缀和应该用平衡树解决，但是这道题常数要求很高，平衡树实现难度也不小，因此不适合使用。

因此，这就用到了一种方法套路：树状数组+离散化干掉平衡树，设 $N$ 为序列长度。

为什么要离散化呢？因为树状数组是建立在值域上的数据结构，不离散化会爆。

我们把关键码 $A$ 数组 离散化到 $[2,N+1]$ 之间，设 $l(x)$ 为离散化后的值,添加一个数 $A(0)=-∞$,然后让 $l(A_0)=1$,在 $[1,N+1] $ 上建立树状数组，初始为零。插入决策为单点修改，查询即可前缀和。

脚本宝典总结

以上是脚本宝典为你收集整理的题解【UVA12983 The Battle of Chibi】全部内容，希望文章能够帮你解决题解【UVA12983 The Battle of Chibi】所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。