差分入门
题单介绍
差分入门题目,适合差分初学者。
### 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 天天爱跑步(对操作进行差分)