社区讨论

关于主席树写法update这么写的原理

P3939数颜色参与者 6已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@lo9lh75f
此快照首次捕获于
2023/10/28 13:21
2 年前
此快照最后确认于
2023/10/28 13:21
2 年前
查看原帖
我是按照题解的思路,按权值建一棵主席树,上面说的update的方式是只改 xx 子树,先让这棵子树的 axa_x 减一,再让 ax+1a_{x+1} 都加上一,这样做的原理是什么,为什么我觉得这样做对后面的子树无法产生影响,会导致区间查询时出现前面的数已经用过了,后面的数还没查到呢?

回复

9 条回复,欢迎继续交流。

正在加载回复...