标签: Binary Indexed Tree

评分 0, 满分 5 星
0 票

由于不确定元素的范围,为了保证程序的正确运行同时节省空间开销,首先对原数组进行离散化。由于BIT可以快速统计在当前位置之前的并且不大于当前元素的元素的数目,而题目要求统计右侧区间因此就需要把离散化后的数组反转后再进行更新和统计,统计完结果之后再把结果反转。

评分 0, 满分 5 星
0 票

好久不写树状数组,几乎要忘记了...这个题目是树状数组和线段树在点修改区间查询上的典型应用。只是感觉函数的参数列表在这里设计的太不合理了,需要重新开一个空间对原数组进行复制才能在非构造函数中调用。还需要注意的就是树状数组下标从1开始,否则在进行lowbit操作的时候有可能陷入死循环。// 魂淡室友看我写题就不等我了,竟然忍心让我凌晨回宿舍,真是魂淡啊...