Divide and Conquer on Segment Trees

Posted on Edited on

线段树分治

实现

动态问题(元素存在生存周期)/无可减性的区间询问

  1. 使用线段树上DFS(CDQ)实现.
  2. 将元素按生存周期拆成\(O(\log n)\)个/将询问按下标拆成\(O(\log n)\)个.
  3. 需要支持元素插入/回滚操作.
  • 特殊情况可以使用BFS,需支持对DS统计信息的重置. ### 静态问题,难以删除元素 例: 整体二分
  1. 可以BFS实现
  2. 将询问按下标/值域拆成\(O(\log n)\)个.
  3. 需要支持插入/清空操作. ## 按问题类型 ### lifespan LOJ #6515. 「雅礼集训 2018 Day10」贪玩蓝月 ### 对询问分治 ZR #2180. 矩阵 ### parallel binary search AGC002 D - Stamp Rally