差分入门

题单介绍

差分入门题目,适合差分初学者。 ### Part 1 学习资料 - [[顾z]差分数组 and 树上差分](https://www.luogu.com.cn/blog/RPdreamer/ci-fen-and-shu-shang-ci-fen) - [[Chanis] 可以代替线段树的树状数组?——树状数组进阶(1)](https://www.luogu.com.cn/blog/Chanis/super-BIT) 在此致谢。 ### Part 2 分层练习 #### Ⅰ.序列差分 序列上的差分能快速进行修改。这里在 @顾z 的基础上增加了更为入门的题目。 - P2367 语文成绩(序列差分模板) - P5026 Lycanthropy - P4231 三步必杀 - AT2442 フェーン現象 (Foehn Phenomena) - P3948 数据结构 - P1083 借教室 - P4552 [Poetize6] IncDec Sequence - P3943 星空 #### Ⅱ.差分与树状数组 树状数组进行差分可以完成区间修改和查询操作。 以下内容请使用树状数组实现。 这里的题如果完成了,可以在使用线段树的很多场合改用树状数组降低常数。因此不附过多练习。 - P3368 【模板】树状数组 2 - P4868 Preprefix sum(有利于帮助区间修改与查询的理解) - P3372 【模板】线段树 1 - P1438 无聊的数列 - P4514 上帝造题的七分钟(二维树状数组+差分) #### Ⅲ.树上差分 树上差分可实现同时对一条路径上的所有点权或边权的快速加减。 - P3128 [USACO15DEC]Max Flow P(边差分模板) - P3258 [JLOI2014]松鼠的新家(点差分模板) - P2680 运输计划 - CF555E Case of Computer Network - P1600 天天爱跑步(对操作进行差分)

题目列表

  • 语文成绩
  • Lycanthropy
  • 三步必杀
  • フェーン現象 (Foehn Phenomena)
  • 数据结构
  • [NOIP2012 提高组] 借教室
  • [Poetize6] IncDec Sequence
  • 星空
  • 【模板】树状数组 2
  • Preprefix sum
  • 【模板】线段树 1
  • 无聊的数列
  • 上帝造题的七分钟
  • [USACO15DEC] Max Flow P
  • [JLOI2014] 松鼠的新家
  • [NOIP2015 提高组] 运输计划
  • Case of Computer Network
  • [NOIP2016 提高组] 天天爱跑步