求势能线段树时间复杂度证明
  • 板块学术版
  • 楼主ziyistudy
  • 当前回复14
  • 已保存回复14
  • 发布时间2024/8/1 15:47
  • 上次更新2024/8/1 16:45:44
查看原帖
求势能线段树时间复杂度证明
462558
ziyistudy楼主2024/8/1 15:47

形象化地,需要支持以下操作。

  1. 区间加操作

  2. 区间除法操作

  3. 区间求和

1≤n,q≤1051\leq n,q\leq 10^5

采用势能线段树一般思想,当区间操作后减少的值相等时,直接区间赋tag,否则继续递归下去。

2024/8/1 15:47
加载中...