前缀和与差分prefix_sum and difference-摩杜云开发者社区

前缀和与差分
- 笔记&模板
  - 前缀和与差分prefix_sum and difference - 唔知叫咩emm - 博客园 (cnblogs.com)
  - 不适合做代码笔记，复习主要是复习思路，要看就看模板题
    - 常用代码模板1——基础算法 - AcWing
  - 注意：左留一个0，避免分类讨论
    - 注意：初始化数组大小，记得+1
- 简介
  - 前缀和是一种重要的预处理，能大大降低查询的时间复杂度
  - 前缀和
    - 数列的前n项的和
  - 差分
    - 差分是一种和前缀和相对的策略，可以当做是求和的逆运算。差分数组的前缀和数组是原数组
- 应用场景，关键词
  - 区间信息维护与查询
- 视频教程
  - STUACM-算法入门-前缀和与差分(含二维)_哔哩哔哩_bilibili
    - 有点长，不太推荐，找个模板题看看题解就能学会
- 知识点&例题
  - 前缀和
    - 一维
      - 303. 区域和检索 - 数组不可变 - 力扣（LeetCode）
        
        力扣模板题（纯模板）
      - B3612 【深进1.例1】求区间和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
        洛谷模板题
      - P5638 【CSGRound2】光骓者的荣耀 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
        稍微复杂一点的前缀和：取不连续段
      - CF1709B Also Try Minecraft - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
        稍微复杂一点的前缀和：双向的前缀和
      - P6625 [省选联考 2020 B 卷] 卡牌游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
        前缀和+贪心
        
        读题4+想题4+写题15=23
      - P1114 “非常男女”计划 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
        【黄题】前缀和，相对差（用两个桶）
      - P3662 [USACO17FEB]Why Did the Cow Cross the Road II S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
        【黄题】
        
        读题1+想题24+写题5=30min
    - 二维
      - 304. 二维区域和检索 - 矩阵不可变 - 力扣（LeetCode）
        
        力扣模板题（纯模板）
      - P2004 领地选择 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
        洛谷模板题
      - P2280 [HNOI2003]激光炸弹 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
        几乎模板题
  - 差分
    - 一维
      - 1109. 航班预订统计 - 力扣（LeetCode）
        
        力扣模板题
      - P2367 语文成绩 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
        洛谷模板题
      - 1094. 拼车 - 力扣（LeetCode）
        
        小变式
      - P3406 海底高铁 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
        变式
    - 二维
      - P3397 地毯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
        模板题
      - P5542 [USACO19FEB]Painting The Barn S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
        模板题

/*Prefix_sum_And_Difference.cpp*/

//不适合做代码笔记，复习主要是复习思路，要看就看模板题