- 前缀和与差分
- 笔记&模板
- 前缀和与差分prefix_sum and difference – 唔知叫咩emm – 博客园 (cnblogs.com)
- 不适合做代码笔记,复习主要是复习思路,要看就看模板题
- 简介
- 前缀和是一种重要的预处理,能大大降低查询的时间复杂度
- 差分
- 差分是一种和前缀和相对的策略,可以当做是求和的逆运算。差分数组的前缀和数组是原数组
- 视频教程
- STUACM-算法入门-前缀和与差分(含二维)_哔哩哔哩_bilibili
- 知识点&例题
- 前缀和
- 一维
- 303. 区域和检索 – 数组不可变 – 力扣(LeetCode)
- B3612 【深进1.例1】求区间和 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
- P5638 【CSGRound2】光骓者的荣耀 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
- CF1709B Also Try Minecraft – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
- 二维
- 304. 二维区域和检索 – 矩阵不可变 – 力扣(LeetCode)
- P2004 领地选择 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
- P2280 [HNOI2003]激光炸弹 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
- 差分
- 一维
- 1109. 航班预订统计 – 力扣(LeetCode)
- P2367 语文成绩 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
- P3406 海底高铁 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
- 二维
- P3397 地毯 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
/*Prefix_sum_And_Difference.cpp*///不适合做代码笔记,复习主要是复习思路,要看就看模板题