列队中对询问离线排序后如何建立树状数组

发布时间 2023-12-17 12:04:17作者: 最爱丁珰

假设\(m=5\)(注意值存储前\(m-1\)个人)

注意我们并没有在方框里面填上具体编号,因为从下文就可以知道这是无关紧要的

假设我们删除了第二个人

绿色方框是新进来的一个人,红色斜杠表示被删除掉的(但是在代码中我们不会真正的删除这一个位置)

那么如果要删除这行中的第二个人,等价于删除以上数组的第三个数,如果要删除这行中的第四个人,等价于删除这个数组的第五个数

假设我们删除了这个数组中的第四个人(即实际删除当前队列中的第四个人)

那么此时删除当前队列中的第四个人等价于删除以上数组的第六个数

如果删除当前队列中的第五个人,那么就是在实际方阵的最后一列进行操作,以上数组不变

所以我们预处理出来的删除数指的是实际删除数,即以上数组的第几个位置

注意以上数组的黑框框实际上是不会存储的而且具体数字是定下来的,从\(1\)\(m-1\)