差分、树上差分

差分入门题目，适合差分初学者。 这份是转来的题单，后期会持续更新 ### 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 dalao 的基础上增加了更为入门的题目。 - [P2367 语文成绩](https://www.luogu.com.cn/problem/P2367) ### - [P5026 Lycanthropy](https://www.luogu.com.cn/problem/P5026) 强力推荐之后很多题都是这种解法 - [P4231 三步必杀](https://www.luogu.com.cn/problem/P4231) - [AT2442 フェーン現象 (Foehn Phenomena)](https://www.luogu.com.cn/problem/AT2442) - [P3948 数据结构](https://www.luogu.com.cn/problem/P3948) - [P1083 [NOIP2012 提高组] 借教室](https://www.luogu.com.cn/problem/P1083)（妙） - [P3943 星空](https://www.luogu.com.cn/problem/P3943) #### Ⅱ.差分与树状数组 树状数组进行差分可以完成区间修改和查询操作。 以下内容请使用树状数组实现。 这里的题如果完成了，可以在使用线段树的很多场合改用树状数组降低常数。因此不附过多练习。 - [P3368 【模板】树状数组 2](https://www.luogu.com.cn/problem/P3368) - [P4868 Preprefix sum](https://www.luogu.com.cn/problem/P4868) - [P3372 【模板】线段树 1](https://www.luogu.com.cn/problem/P3372) - [P1438 无聊的数列](https://www.luogu.com.cn/problem/P1438) - [P4514 上帝造题的七分钟](https://www.luogu.com.cn/problem/P4514) #### Ⅲ.树上差分 树上差分可实现同时对一条路径上的所有点权或边权的快速加减。 在此感谢上次发求助帖时回复我的各位。 - [P3128 [USACO15DEC]Max Flow P](https://www.luogu.com.cn/problem/P3128) - [P3258 [JLOI2014]松鼠的新家](https://www.luogu.com.cn/problem/P3258) - [P2680 [NOIP2015 提高组] 运输计划](https://www.luogu.com.cn/problem/P2680) - [CF555E Case of Computer Network](https://www.luogu.com.cn/problem/CF555E) - [P1600 [NOIP2016 提高组] 天天爱跑步](https://www.luogu.com.cn/problem/P1600)