前缀和与差分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)
          
          • 稍微复杂一点的前缀和：双向的前缀和
            
      • 二维
        
        • 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)
          
          • 模板题
            

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