【算法专题·第五章】前缀和与差分

前缀和与差分：一对互逆操作，把区间问题从O(n)降到O(1)的终极武器

前缀和与差分是算法中最被低估的技巧——概念简单到5分钟就能讲完，但面试中能灵活运用的人不到20%。我在面试中问过"如何O(1)时间求任意子数组之和"，大部分人能答出前缀和；但追问"如何O(1)时间对区间统一加一个数"，能答出差分的人不到一半；再追问"二维前缀和的容斥原理怎么推"，大部分人就卡壳了。这篇文章把前缀和与差分作为一对互逆操作来讲——前缀和是"积"（从差到和），差分是"拆"（从和到差），理解了这个互逆关系，所有变形题都能秒杀。

〇、全文导航

#mermaid-svg-1olbwZisErYhR4Hm{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-1olbwZisErYhR4Hm .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-1olbwZisErYhR4Hm .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-1olbwZisErYhR4Hm .error-icon{fill:#552222;}#mermaid-svg-1olbwZisErYhR4Hm .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-1olbwZisErYhR4Hm .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-1olbwZisErYhR4Hm .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-1olbwZisErYhR4Hm .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-1olbwZisErYhR4Hm .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-1olbwZisErYhR4Hm .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-1olbwZisErYhR4Hm .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-1olbwZisErYhR4Hm .marker{fill:#333333;stroke:#333333;}#mermaid-svg-1olbwZisErYhR4Hm .marker.cross{stroke:#333333;}#mermaid-svg-1olbwZisErYhR4Hm svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-1olbwZisErYhR4Hm p{margin:0;}#mermaid-svg-1olbwZisErYhR4Hm .edge{stroke-width:3;}#mermaid-svg-1olbwZisErYhR4Hm .section–1 rect,#mermaid-svg-1olbwZisErYhR4Hm .section–1 path,#mermaid-svg-1olbwZisErYhR4Hm .section–1 circle,#mermaid-svg-1olbwZisErYhR4Hm .section–1 polygon,#mermaid-svg-1olbwZisErYhR4Hm .section–1 path{fill:hsl(240, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .section–1 text{fill:#ffffff;}#mermaid-svg-1olbwZisErYhR4Hm .node-icon–1{font-size:40px;color:#ffffff;}#mermaid-svg-1olbwZisErYhR4Hm .section-edge–1{stroke:hsl(240, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .edge-depth–1{stroke-width:17;}#mermaid-svg-1olbwZisErYhR4Hm .section–1 line{stroke:hsl(60, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-1olbwZisErYhR4Hm .disabled,#mermaid-svg-1olbwZisErYhR4Hm .disabled circle,#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:lightgray;}#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:#efefef;}#mermaid-svg-1olbwZisErYhR4Hm .section-0 rect,#mermaid-svg-1olbwZisErYhR4Hm .section-0 path,#mermaid-svg-1olbwZisErYhR4Hm .section-0 circle,#mermaid-svg-1olbwZisErYhR4Hm .section-0 polygon,#mermaid-svg-1olbwZisErYhR4Hm .section-0 path{fill:hsl(60, 100%, 73.5294117647%);}#mermaid-svg-1olbwZisErYhR4Hm .section-0 text{fill:black;}#mermaid-svg-1olbwZisErYhR4Hm .node-icon-0{font-size:40px;color:black;}#mermaid-svg-1olbwZisErYhR4Hm .section-edge-0{stroke:hsl(60, 100%, 73.5294117647%);}#mermaid-svg-1olbwZisErYhR4Hm .edge-depth-0{stroke-width:14;}#mermaid-svg-1olbwZisErYhR4Hm .section-0 line{stroke:hsl(240, 100%, 83.5294117647%);stroke-width:3;}#mermaid-svg-1olbwZisErYhR4Hm .disabled,#mermaid-svg-1olbwZisErYhR4Hm .disabled circle,#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:lightgray;}#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:#efefef;}#mermaid-svg-1olbwZisErYhR4Hm .section-1 rect,#mermaid-svg-1olbwZisErYhR4Hm .section-1 path,#mermaid-svg-1olbwZisErYhR4Hm .section-1 circle,#mermaid-svg-1olbwZisErYhR4Hm .section-1 polygon,#mermaid-svg-1olbwZisErYhR4Hm .section-1 path{fill:hsl(80, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .section-1 text{fill:black;}#mermaid-svg-1olbwZisErYhR4Hm .node-icon-1{font-size:40px;color:black;}#mermaid-svg-1olbwZisErYhR4Hm .section-edge-1{stroke:hsl(80, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .edge-depth-1{stroke-width:11;}#mermaid-svg-1olbwZisErYhR4Hm .section-1 line{stroke:hsl(260, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-1olbwZisErYhR4Hm .disabled,#mermaid-svg-1olbwZisErYhR4Hm .disabled circle,#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:lightgray;}#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:#efefef;}#mermaid-svg-1olbwZisErYhR4Hm .section-2 rect,#mermaid-svg-1olbwZisErYhR4Hm .section-2 path,#mermaid-svg-1olbwZisErYhR4Hm .section-2 circle,#mermaid-svg-1olbwZisErYhR4Hm .section-2 polygon,#mermaid-svg-1olbwZisErYhR4Hm .section-2 path{fill:hsl(270, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .section-2 text{fill:#ffffff;}#mermaid-svg-1olbwZisErYhR4Hm .node-icon-2{font-size:40px;color:#ffffff;}#mermaid-svg-1olbwZisErYhR4Hm .section-edge-2{stroke:hsl(270, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .edge-depth-2{stroke-width:8;}#mermaid-svg-1olbwZisErYhR4Hm .section-2 line{stroke:hsl(90, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-1olbwZisErYhR4Hm .disabled,#mermaid-svg-1olbwZisErYhR4Hm .disabled circle,#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:lightgray;}#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:#efefef;}#mermaid-svg-1olbwZisErYhR4Hm .section-3 rect,#mermaid-svg-1olbwZisErYhR4Hm .section-3 path,#mermaid-svg-1olbwZisErYhR4Hm .section-3 circle,#mermaid-svg-1olbwZisErYhR4Hm .section-3 polygon,#mermaid-svg-1olbwZisErYhR4Hm .section-3 path{fill:hsl(300, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .section-3 text{fill:black;}#mermaid-svg-1olbwZisErYhR4Hm .node-icon-3{font-size:40px;color:black;}#mermaid-svg-1olbwZisErYhR4Hm .section-edge-3{stroke:hsl(300, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .edge-depth-3{stroke-width:5;}#mermaid-svg-1olbwZisErYhR4Hm .section-3 line{stroke:hsl(120, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-1olbwZisErYhR4Hm .disabled,#mermaid-svg-1olbwZisErYhR4Hm .disabled circle,#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:lightgray;}#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:#efefef;}#mermaid-svg-1olbwZisErYhR4Hm .section-4 rect,#mermaid-svg-1olbwZisErYhR4Hm .section-4 path,#mermaid-svg-1olbwZisErYhR4Hm .section-4 circle,#mermaid-svg-1olbwZisErYhR4Hm .section-4 polygon,#mermaid-svg-1olbwZisErYhR4Hm .section-4 path{fill:hsl(330, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .section-4 text{fill:black;}#mermaid-svg-1olbwZisErYhR4Hm .node-icon-4{font-size:40px;color:black;}#mermaid-svg-1olbwZisErYhR4Hm .section-edge-4{stroke:hsl(330, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .edge-depth-4{stroke-width:2;}#mermaid-svg-1olbwZisErYhR4Hm .section-4 line{stroke:hsl(150, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-1olbwZisErYhR4Hm .disabled,#mermaid-svg-1olbwZisErYhR4Hm .disabled circle,#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:lightgray;}#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:#efefef;}#mermaid-svg-1olbwZisErYhR4Hm .section-5 rect,#mermaid-svg-1olbwZisErYhR4Hm .section-5 path,#mermaid-svg-1olbwZisErYhR4Hm .section-5 circle,#mermaid-svg-1olbwZisErYhR4Hm .section-5 polygon,#mermaid-svg-1olbwZisErYhR4Hm .section-5 path{fill:hsl(0, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .section-5 text{fill:black;}#mermaid-svg-1olbwZisErYhR4Hm .node-icon-5{font-size:40px;color:black;}#mermaid-svg-1olbwZisErYhR4Hm .section-edge-5{stroke:hsl(0, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .edge-depth-5{stroke-width:-1;}#mermaid-svg-1olbwZisErYhR4Hm .section-5 line{stroke:hsl(180, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-1olbwZisErYhR4Hm .disabled,#mermaid-svg-1olbwZisErYhR4Hm .disabled circle,#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:lightgray;}#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:#efefef;}#mermaid-svg-1olbwZisErYhR4Hm .section-6 rect,#mermaid-svg-1olbwZisErYhR4Hm .section-6 path,#mermaid-svg-1olbwZisErYhR4Hm .section-6 circle,#mermaid-svg-1olbwZisErYhR4Hm .section-6 polygon,#mermaid-svg-1olbwZisErYhR4Hm .section-6 path{fill:hsl(30, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .section-6 text{fill:black;}#mermaid-svg-1olbwZisErYhR4Hm .node-icon-6{font-size:40px;color:black;}#mermaid-svg-1olbwZisErYhR4Hm .section-edge-6{stroke:hsl(30, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .edge-depth-6{stroke-width:-4;}#mermaid-svg-1olbwZisErYhR4Hm .section-6 line{stroke:hsl(210, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-1olbwZisErYhR4Hm .disabled,#mermaid-svg-1olbwZisErYhR4Hm .disabled circle,#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:lightgray;}#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:#efefef;}#mermaid-svg-1olbwZisErYhR4Hm .section-7 rect,#mermaid-svg-1olbwZisErYhR4Hm .section-7 path,#mermaid-svg-1olbwZisErYhR4Hm .section-7 circle,#mermaid-svg-1olbwZisErYhR4Hm .section-7 polygon,#mermaid-svg-1olbwZisErYhR4Hm .section-7 path{fill:hsl(90, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .section-7 text{fill:black;}#mermaid-svg-1olbwZisErYhR4Hm .node-icon-7{font-size:40px;color:black;}#mermaid-svg-1olbwZisErYhR4Hm .section-edge-7{stroke:hsl(90, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .edge-depth-7{stroke-width:-7;}#mermaid-svg-1olbwZisErYhR4Hm .section-7 line{stroke:hsl(270, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-1olbwZisErYhR4Hm .disabled,#mermaid-svg-1olbwZisErYhR4Hm .disabled circle,#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:lightgray;}#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:#efefef;}#mermaid-svg-1olbwZisErYhR4Hm .section-8 rect,#mermaid-svg-1olbwZisErYhR4Hm .section-8 path,#mermaid-svg-1olbwZisErYhR4Hm .section-8 circle,#mermaid-svg-1olbwZisErYhR4Hm .section-8 polygon,#mermaid-svg-1olbwZisErYhR4Hm .section-8 path{fill:hsl(150, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .section-8 text{fill:black;}#mermaid-svg-1olbwZisErYhR4Hm .node-icon-8{font-size:40px;color:black;}#mermaid-svg-1olbwZisErYhR4Hm .section-edge-8{stroke:hsl(150, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .edge-depth-8{stroke-width:-10;}#mermaid-svg-1olbwZisErYhR4Hm .section-8 line{stroke:hsl(330, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-1olbwZisErYhR4Hm .disabled,#mermaid-svg-1olbwZisErYhR4Hm .disabled circle,#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:lightgray;}#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:#efefef;}#mermaid-svg-1olbwZisErYhR4Hm .section-9 rect,#mermaid-svg-1olbwZisErYhR4Hm .section-9 path,#mermaid-svg-1olbwZisErYhR4Hm .section-9 circle,#mermaid-svg-1olbwZisErYhR4Hm .section-9 polygon,#mermaid-svg-1olbwZisErYhR4Hm .section-9 path{fill:hsl(180, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .section-9 text{fill:black;}#mermaid-svg-1olbwZisErYhR4Hm .node-icon-9{font-size:40px;color:black;}#mermaid-svg-1olbwZisErYhR4Hm .section-edge-9{stroke:hsl(180, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .edge-depth-9{stroke-width:-13;}#mermaid-svg-1olbwZisErYhR4Hm .section-9 line{stroke:hsl(0, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-1olbwZisErYhR4Hm .disabled,#mermaid-svg-1olbwZisErYhR4Hm .disabled circle,#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:lightgray;}#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:#efefef;}#mermaid-svg-1olbwZisErYhR4Hm .section-10 rect,#mermaid-svg-1olbwZisErYhR4Hm .section-10 path,#mermaid-svg-1olbwZisErYhR4Hm .section-10 circle,#mermaid-svg-1olbwZisErYhR4Hm .section-10 polygon,#mermaid-svg-1olbwZisErYhR4Hm .section-10 path{fill:hsl(210, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .section-10 text{fill:black;}#mermaid-svg-1olbwZisErYhR4Hm .node-icon-10{font-size:40px;color:black;}#mermaid-svg-1olbwZisErYhR4Hm .section-edge-10{stroke:hsl(210, 100%, 76.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .edge-depth-10{stroke-width:-16;}#mermaid-svg-1olbwZisErYhR4Hm .section-10 line{stroke:hsl(30, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-1olbwZisErYhR4Hm .disabled,#mermaid-svg-1olbwZisErYhR4Hm .disabled circle,#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:lightgray;}#mermaid-svg-1olbwZisErYhR4Hm .disabled text{fill:#efefef;}#mermaid-svg-1olbwZisErYhR4Hm .section-root rect,#mermaid-svg-1olbwZisErYhR4Hm .section-root path,#mermaid-svg-1olbwZisErYhR4Hm .section-root circle,#mermaid-svg-1olbwZisErYhR4Hm .section-root polygon{fill:hsl(240, 100%, 46.2745098039%);}#mermaid-svg-1olbwZisErYhR4Hm .section-root text{fill:#ffffff;}#mermaid-svg-1olbwZisErYhR4Hm .section-root span{color:#ffffff;}#mermaid-svg-1olbwZisErYhR4Hm .section-2 span{color:#ffffff;}#mermaid-svg-1olbwZisErYhR4Hm .icon-container{height:100%;display:flex;justify-content:center;align-items:center;}#mermaid-svg-1olbwZisErYhR4Hm .edge{fill:none;}#mermaid-svg-1olbwZisErYhR4Hm .mindmap-node-label{dy:1em;alignment-baseline:middle;text-anchor:middle;dominant-baseline:middle;text-align:center;}#mermaid-svg-1olbwZisErYhR4Hm :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

前缀和与差分

核心思想

互逆操作对

积与拆

预处理换查询

一维前缀和

定义与公式

O1区间求和

变形 前缀和+哈希

一维差分

定义与公式

O1区间修改

还原过程

与前缀和的互逆

二维前缀和

容斥原理推导

子矩阵求和

逐帧图解

二维差分

二维差分公式

子矩阵修改

还原过程

LeetCode实战

区间求和类

区间修改类

前缀和+哈希类

二维类

面试备战

高频面试题

模板速查

一、核心思想：一对互逆操作

1.1 一个直觉：银行流水与余额

想象你的银行账户：

日期: 1号 2号 3号 4号 5号 6号 7号
流水(差分): +100 -30 +50 -20 +200 -80 +60
余额(前缀和): 100 70 120 100 300 220 280

• 流水 → 余额：把每天的变动累加起来，就是余额。这就是前缀和。
• 余额 → 流水：用今天的余额减昨天的余额，就是今天的变动。这就是差分。

#mermaid-svg-CTIcO79lTZGWCLVs{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-CTIcO79lTZGWCLVs .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-CTIcO79lTZGWCLVs .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-CTIcO79lTZGWCLVs .error-icon{fill:#552222;}#mermaid-svg-CTIcO79lTZGWCLVs .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-CTIcO79lTZGWCLVs .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-CTIcO79lTZGWCLVs .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-CTIcO79lTZGWCLVs .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-CTIcO79lTZGWCLVs .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-CTIcO79lTZGWCLVs .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-CTIcO79lTZGWCLVs .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-CTIcO79lTZGWCLVs .marker{fill:#333333;stroke:#333333;}#mermaid-svg-CTIcO79lTZGWCLVs .marker.cross{stroke:#333333;}#mermaid-svg-CTIcO79lTZGWCLVs svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-CTIcO79lTZGWCLVs p{margin:0;}#mermaid-svg-CTIcO79lTZGWCLVs .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-CTIcO79lTZGWCLVs .cluster-label text{fill:#333;}#mermaid-svg-CTIcO79lTZGWCLVs .cluster-label span{color:#333;}#mermaid-svg-CTIcO79lTZGWCLVs .cluster-label span p{background-color:transparent;}#mermaid-svg-CTIcO79lTZGWCLVs .label text,#mermaid-svg-CTIcO79lTZGWCLVs span{fill:#333;color:#333;}#mermaid-svg-CTIcO79lTZGWCLVs .node rect,#mermaid-svg-CTIcO79lTZGWCLVs .node circle,#mermaid-svg-CTIcO79lTZGWCLVs .node ellipse,#mermaid-svg-CTIcO79lTZGWCLVs .node polygon,#mermaid-svg-CTIcO79lTZGWCLVs .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-CTIcO79lTZGWCLVs .rough-node .label text,#mermaid-svg-CTIcO79lTZGWCLVs .node .label text,#mermaid-svg-CTIcO79lTZGWCLVs .image-shape .label,#mermaid-svg-CTIcO79lTZGWCLVs .icon-shape .label{text-anchor:middle;}#mermaid-svg-CTIcO79lTZGWCLVs .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-CTIcO79lTZGWCLVs .rough-node .label,#mermaid-svg-CTIcO79lTZGWCLVs .node .label,#mermaid-svg-CTIcO79lTZGWCLVs .image-shape .label,#mermaid-svg-CTIcO79lTZGWCLVs .icon-shape .label{text-align:center;}#mermaid-svg-CTIcO79lTZGWCLVs .node.clickable{cursor:pointer;}#mermaid-svg-CTIcO79lTZGWCLVs .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-CTIcO79lTZGWCLVs .arrowheadPath{fill:#333333;}#mermaid-svg-CTIcO79lTZGWCLVs .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-CTIcO79lTZGWCLVs .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-CTIcO79lTZGWCLVs .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-CTIcO79lTZGWCLVs .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-CTIcO79lTZGWCLVs .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-CTIcO79lTZGWCLVs .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-CTIcO79lTZGWCLVs .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-CTIcO79lTZGWCLVs .cluster text{fill:#333;}#mermaid-svg-CTIcO79lTZGWCLVs .cluster span{color:#333;}#mermaid-svg-CTIcO79lTZGWCLVs div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-CTIcO79lTZGWCLVs .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-CTIcO79lTZGWCLVs rect.text{fill:none;stroke-width:0;}#mermaid-svg-CTIcO79lTZGWCLVs .icon-shape,#mermaid-svg-CTIcO79lTZGWCLVs .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-CTIcO79lTZGWCLVs .icon-shape p,#mermaid-svg-CTIcO79lTZGWCLVs .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-CTIcO79lTZGWCLVs .icon-shape .label rect,#mermaid-svg-CTIcO79lTZGWCLVs .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-CTIcO79lTZGWCLVs .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-CTIcO79lTZGWCLVs .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-CTIcO79lTZGWCLVs :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

前缀和累加

差分相邻相减

差分数组 diff+100, -30, +50, -20, +200, -80, +60

前缀和 preSum100, 70, 120, 100, 300, 220, 280

一句话：前缀和是"积"（累加），差分是"拆"（相减），两者互为逆运算。

1.2 为什么这两个操作重要？

核心思路：用一次 O(n) 的预处理，换后续每次操作 O(1) 的时间——预处理换查询。

二、一维前缀和

2.1 定义

给定数组 a[0..n-1]，前缀和数组 preSum[i] 表示前 i 个元素之和：

preSum[0] = 0
preSum[i] = a[0] + a[1] + … + a[i-1] (1 ≤ i ≤ n)

注意：preSum 比 a 多一个元素，preSum[0] = 0 是哨兵，避免边界判断。

数组 a: [3, 1, 4, 1, 5, 9, 2]
下标: 0 1 2 3 4 5 6

前缀和 preSum: [0, 3, 4, 8, 9, 14, 23, 25]
下标: 0 1 2 3 4 5 6 7

2.2 核心公式：O(1) 区间求和

区间 [l, r] 的和 = preSum[r+1] – preSum[l]

#mermaid-svg-oAqDeZzgMepfZ4b5{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-oAqDeZzgMepfZ4b5 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-oAqDeZzgMepfZ4b5 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-oAqDeZzgMepfZ4b5 .error-icon{fill:#552222;}#mermaid-svg-oAqDeZzgMepfZ4b5 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-oAqDeZzgMepfZ4b5 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-oAqDeZzgMepfZ4b5 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-oAqDeZzgMepfZ4b5 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-oAqDeZzgMepfZ4b5 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-oAqDeZzgMepfZ4b5 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-oAqDeZzgMepfZ4b5 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-oAqDeZzgMepfZ4b5 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-oAqDeZzgMepfZ4b5 .marker.cross{stroke:#333333;}#mermaid-svg-oAqDeZzgMepfZ4b5 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-oAqDeZzgMepfZ4b5 p{margin:0;}#mermaid-svg-oAqDeZzgMepfZ4b5 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-oAqDeZzgMepfZ4b5 .cluster-label text{fill:#333;}#mermaid-svg-oAqDeZzgMepfZ4b5 .cluster-label span{color:#333;}#mermaid-svg-oAqDeZzgMepfZ4b5 .cluster-label span p{background-color:transparent;}#mermaid-svg-oAqDeZzgMepfZ4b5 .label text,#mermaid-svg-oAqDeZzgMepfZ4b5 span{fill:#333;color:#333;}#mermaid-svg-oAqDeZzgMepfZ4b5 .node rect,#mermaid-svg-oAqDeZzgMepfZ4b5 .node circle,#mermaid-svg-oAqDeZzgMepfZ4b5 .node ellipse,#mermaid-svg-oAqDeZzgMepfZ4b5 .node polygon,#mermaid-svg-oAqDeZzgMepfZ4b5 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-oAqDeZzgMepfZ4b5 .rough-node .label text,#mermaid-svg-oAqDeZzgMepfZ4b5 .node .label text,#mermaid-svg-oAqDeZzgMepfZ4b5 .image-shape .label,#mermaid-svg-oAqDeZzgMepfZ4b5 .icon-shape .label{text-anchor:middle;}#mermaid-svg-oAqDeZzgMepfZ4b5 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-oAqDeZzgMepfZ4b5 .rough-node .label,#mermaid-svg-oAqDeZzgMepfZ4b5 .node .label,#mermaid-svg-oAqDeZzgMepfZ4b5 .image-shape .label,#mermaid-svg-oAqDeZzgMepfZ4b5 .icon-shape .label{text-align:center;}#mermaid-svg-oAqDeZzgMepfZ4b5 .node.clickable{cursor:pointer;}#mermaid-svg-oAqDeZzgMepfZ4b5 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-oAqDeZzgMepfZ4b5 .arrowheadPath{fill:#333333;}#mermaid-svg-oAqDeZzgMepfZ4b5 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-oAqDeZzgMepfZ4b5 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-oAqDeZzgMepfZ4b5 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-oAqDeZzgMepfZ4b5 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-oAqDeZzgMepfZ4b5 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-oAqDeZzgMepfZ4b5 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-oAqDeZzgMepfZ4b5 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-oAqDeZzgMepfZ4b5 .cluster text{fill:#333;}#mermaid-svg-oAqDeZzgMepfZ4b5 .cluster span{color:#333;}#mermaid-svg-oAqDeZzgMepfZ4b5 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-oAqDeZzgMepfZ4b5 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-oAqDeZzgMepfZ4b5 rect.text{fill:none;stroke-width:0;}#mermaid-svg-oAqDeZzgMepfZ4b5 .icon-shape,#mermaid-svg-oAqDeZzgMepfZ4b5 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-oAqDeZzgMepfZ4b5 .icon-shape p,#mermaid-svg-oAqDeZzgMepfZ4b5 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-oAqDeZzgMepfZ4b5 .icon-shape .label rect,#mermaid-svg-oAqDeZzgMepfZ4b5 .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-oAqDeZzgMepfZ4b5 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-oAqDeZzgMepfZ4b5 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-oAqDeZzgMepfZ4b5 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

前缀和数组

preSum[0]=0

preSum[1]=3

preSum[2]=4

preSum[3]=8

preSum[4]=9

preSum[5]=14

preSum[6]=23

preSum[7]=25

求 a[2..5] 的和= a[2]+a[3]+a[4]+a[5]= 4+1+5+9 = 19

= preSum[6] – preSum[2]= 23 – 4 = 19 ✅

为什么？ preSum[r+1] 是 [0..r] 的和，preSum[l] 是 [0..l-1] 的和，相减就是 [l..r] 的和。

2.3 代码实现

// 一维前缀和
class PrefixSum {
private int[] preSum;

// O(n) 预处理
public PrefixSum(int[] nums) {
int n = nums.length;
preSum = new int[n + 1];
for (int i = 0; i < n; i++) {
preSum[i + 1] = preSum[i] + nums[i];
}
}

// O(1) 查询区间 [l, r] 的和
public int sumRange(int l, int r) {
return preSum[r + 1] – preSum[l];
}
}

2.4 变形：前缀和 + 哈希

前缀和不仅能求区间和，还能解决"和为K的子数组"问题——这是前缀和最灵活的用法。

问题：给定数组，求和为 K 的连续子数组个数。

思路：如果 preSum[j] – preSum[i] = K，则区间 [i, j-1] 的和为 K。等价于：对于每个 preSum[j]，找前面有多少个 preSum[i] = preSum[j] – K。

// LeetCode 560: 和为 K 的子数组
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
count.put(0, 1); // preSum[0] = 0 出现1次

int preSum = 0, result = 0;
for (int num : nums) {
preSum += num;
// 找前面有多少个 preSum[i] = preSum – k
result += count.getOrDefault(preSum – k, 0);
// 当前 preSum 加入哈希表
count.merge(preSum, 1, Integer::sum);
}
return result;
}

#mermaid-svg-teXC278PDkJCNzxP{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-teXC278PDkJCNzxP .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-teXC278PDkJCNzxP .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-teXC278PDkJCNzxP .error-icon{fill:#552222;}#mermaid-svg-teXC278PDkJCNzxP .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-teXC278PDkJCNzxP .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-teXC278PDkJCNzxP .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-teXC278PDkJCNzxP .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-teXC278PDkJCNzxP .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-teXC278PDkJCNzxP .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-teXC278PDkJCNzxP .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-teXC278PDkJCNzxP .marker{fill:#333333;stroke:#333333;}#mermaid-svg-teXC278PDkJCNzxP .marker.cross{stroke:#333333;}#mermaid-svg-teXC278PDkJCNzxP svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-teXC278PDkJCNzxP p{margin:0;}#mermaid-svg-teXC278PDkJCNzxP .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-teXC278PDkJCNzxP .cluster-label text{fill:#333;}#mermaid-svg-teXC278PDkJCNzxP .cluster-label span{color:#333;}#mermaid-svg-teXC278PDkJCNzxP .cluster-label span p{background-color:transparent;}#mermaid-svg-teXC278PDkJCNzxP .label text,#mermaid-svg-teXC278PDkJCNzxP span{fill:#333;color:#333;}#mermaid-svg-teXC278PDkJCNzxP .node rect,#mermaid-svg-teXC278PDkJCNzxP .node circle,#mermaid-svg-teXC278PDkJCNzxP .node ellipse,#mermaid-svg-teXC278PDkJCNzxP .node polygon,#mermaid-svg-teXC278PDkJCNzxP .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-teXC278PDkJCNzxP .rough-node .label text,#mermaid-svg-teXC278PDkJCNzxP .node .label text,#mermaid-svg-teXC278PDkJCNzxP .image-shape .label,#mermaid-svg-teXC278PDkJCNzxP .icon-shape .label{text-anchor:middle;}#mermaid-svg-teXC278PDkJCNzxP .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-teXC278PDkJCNzxP .rough-node .label,#mermaid-svg-teXC278PDkJCNzxP .node .label,#mermaid-svg-teXC278PDkJCNzxP .image-shape .label,#mermaid-svg-teXC278PDkJCNzxP .icon-shape .label{text-align:center;}#mermaid-svg-teXC278PDkJCNzxP .node.clickable{cursor:pointer;}#mermaid-svg-teXC278PDkJCNzxP .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-teXC278PDkJCNzxP .arrowheadPath{fill:#333333;}#mermaid-svg-teXC278PDkJCNzxP .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-teXC278PDkJCNzxP .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-teXC278PDkJCNzxP .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-teXC278PDkJCNzxP .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-teXC278PDkJCNzxP .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-teXC278PDkJCNzxP .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-teXC278PDkJCNzxP .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-teXC278PDkJCNzxP .cluster text{fill:#333;}#mermaid-svg-teXC278PDkJCNzxP .cluster span{color:#333;}#mermaid-svg-teXC278PDkJCNzxP div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-teXC278PDkJCNzxP .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-teXC278PDkJCNzxP rect.text{fill:none;stroke-width:0;}#mermaid-svg-teXC278PDkJCNzxP .icon-shape,#mermaid-svg-teXC278PDkJCNzxP .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-teXC278PDkJCNzxP .icon-shape p,#mermaid-svg-teXC278PDkJCNzxP .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-teXC278PDkJCNzxP .icon-shape .label rect,#mermaid-svg-teXC278PDkJCNzxP .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-teXC278PDkJCNzxP .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-teXC278PDkJCNzxP .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-teXC278PDkJCNzxP :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

遍历数组，维护 preSum

对于当前 preSum查找 preSum – K 出现了几次

那几次就是以当前位置结尾的和为K的子数组个数

将当前 preSum 存入哈希表

关键细节：count.put(0, 1) 不能忘——它代表空前缀，处理子数组从开头开始的情况。

三、一维差分

3.1 定义

给定数组 a[0..n-1]，差分数组 diff[i] 定义为：

diff[0] = a[0]
diff[i] = a[i] – a[i-1] (1 ≤ i ≤ n-1)

数组 a: [3, 1, 4, 1, 5, 9, 2]
差分 diff: [3, -2, 3, -3, 4, 4, -7]

验证：diff 做前缀和 → [3, 1, 4, 1, 5, 9, 2] = 原数组 ✅

3.2 核心公式：O(1) 区间修改

问题：对区间 [l, r] 每个元素加 val。

暴力做法：遍历 [l, r] 逐个加，O(n)。

差分做法：只改两个位置，O(1)。

diff[l] += val
diff[r + 1] -= val (如果 r + 1 < n)

为什么？ diff[l] += val 使得从 l 开始，前缀和都多了 val；diff[r+1] -= val 使得从 r+1 开始，前缀和又减回 val——效果就是只有 [l, r] 加了 val。

#mermaid-svg-3eTRwEfTIQM5riO9{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-3eTRwEfTIQM5riO9 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-3eTRwEfTIQM5riO9 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-3eTRwEfTIQM5riO9 .error-icon{fill:#552222;}#mermaid-svg-3eTRwEfTIQM5riO9 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-3eTRwEfTIQM5riO9 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-3eTRwEfTIQM5riO9 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-3eTRwEfTIQM5riO9 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-3eTRwEfTIQM5riO9 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-3eTRwEfTIQM5riO9 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-3eTRwEfTIQM5riO9 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-3eTRwEfTIQM5riO9 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-3eTRwEfTIQM5riO9 .marker.cross{stroke:#333333;}#mermaid-svg-3eTRwEfTIQM5riO9 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-3eTRwEfTIQM5riO9 p{margin:0;}#mermaid-svg-3eTRwEfTIQM5riO9 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-3eTRwEfTIQM5riO9 .cluster-label text{fill:#333;}#mermaid-svg-3eTRwEfTIQM5riO9 .cluster-label span{color:#333;}#mermaid-svg-3eTRwEfTIQM5riO9 .cluster-label span p{background-color:transparent;}#mermaid-svg-3eTRwEfTIQM5riO9 .label text,#mermaid-svg-3eTRwEfTIQM5riO9 span{fill:#333;color:#333;}#mermaid-svg-3eTRwEfTIQM5riO9 .node rect,#mermaid-svg-3eTRwEfTIQM5riO9 .node circle,#mermaid-svg-3eTRwEfTIQM5riO9 .node ellipse,#mermaid-svg-3eTRwEfTIQM5riO9 .node polygon,#mermaid-svg-3eTRwEfTIQM5riO9 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-3eTRwEfTIQM5riO9 .rough-node .label text,#mermaid-svg-3eTRwEfTIQM5riO9 .node .label text,#mermaid-svg-3eTRwEfTIQM5riO9 .image-shape .label,#mermaid-svg-3eTRwEfTIQM5riO9 .icon-shape .label{text-anchor:middle;}#mermaid-svg-3eTRwEfTIQM5riO9 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-3eTRwEfTIQM5riO9 .rough-node .label,#mermaid-svg-3eTRwEfTIQM5riO9 .node .label,#mermaid-svg-3eTRwEfTIQM5riO9 .image-shape .label,#mermaid-svg-3eTRwEfTIQM5riO9 .icon-shape .label{text-align:center;}#mermaid-svg-3eTRwEfTIQM5riO9 .node.clickable{cursor:pointer;}#mermaid-svg-3eTRwEfTIQM5riO9 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-3eTRwEfTIQM5riO9 .arrowheadPath{fill:#333333;}#mermaid-svg-3eTRwEfTIQM5riO9 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-3eTRwEfTIQM5riO9 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-3eTRwEfTIQM5riO9 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-3eTRwEfTIQM5riO9 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-3eTRwEfTIQM5riO9 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-3eTRwEfTIQM5riO9 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-3eTRwEfTIQM5riO9 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-3eTRwEfTIQM5riO9 .cluster text{fill:#333;}#mermaid-svg-3eTRwEfTIQM5riO9 .cluster span{color:#333;}#mermaid-svg-3eTRwEfTIQM5riO9 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-3eTRwEfTIQM5riO9 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-3eTRwEfTIQM5riO9 rect.text{fill:none;stroke-width:0;}#mermaid-svg-3eTRwEfTIQM5riO9 .icon-shape,#mermaid-svg-3eTRwEfTIQM5riO9 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-3eTRwEfTIQM5riO9 .icon-shape p,#mermaid-svg-3eTRwEfTIQM5riO9 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-3eTRwEfTIQM5riO9 .icon-shape .label rect,#mermaid-svg-3eTRwEfTIQM5riO9 .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-3eTRwEfTIQM5riO9 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-3eTRwEfTIQM5riO9 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-3eTRwEfTIQM5riO9 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

还原后的数组

差分数组diff

原数组a

a[0]=3

a[1]=1

a[2]=4

a[3]=1

a[4]=5

a[5]=9

a[6]=2

对区间 [2, 4] 每个元素 +10

diff[0]=3

diff[1]=-2

diff[2]=3+10=13

diff[3]=-3

diff[4]=4

diff[5]=4-10=-6

diff[6]=-7

3

1

14

11

15

9

2

3.3 完整代码

// 一维差分
class Difference {
private int[] diff;
private int n;

// O(n) 初始化
public Difference(int[] nums) {
n = nums.length;
diff = new int[n];
diff[0] = nums[0];
for (int i = 1; i < n; i++) {
diff[i] = nums[i] – nums[i – 1];
}
}

// O(1) 区间 [l, r] 每个元素加 val
public void increment(int l, int r, int val) {
diff[l] += val;
if (r + 1 < n) {
diff[r + 1] -= val;
}
}

// O(n) 还原数组
public int[] result() {
int[] res = new int[n];
res[0] = diff[0];
for (int i = 1; i < n; i++) {
res[i] = res[i – 1] + diff[i];
}
return res;
}
}

3.4 前缀和与差分的互逆关系

#mermaid-svg-4VdXkOKkTOAnmd8Y{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-4VdXkOKkTOAnmd8Y .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-4VdXkOKkTOAnmd8Y .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-4VdXkOKkTOAnmd8Y .error-icon{fill:#552222;}#mermaid-svg-4VdXkOKkTOAnmd8Y .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-4VdXkOKkTOAnmd8Y .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-4VdXkOKkTOAnmd8Y .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-4VdXkOKkTOAnmd8Y .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-4VdXkOKkTOAnmd8Y .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-4VdXkOKkTOAnmd8Y .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-4VdXkOKkTOAnmd8Y .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-4VdXkOKkTOAnmd8Y .marker{fill:#333333;stroke:#333333;}#mermaid-svg-4VdXkOKkTOAnmd8Y .marker.cross{stroke:#333333;}#mermaid-svg-4VdXkOKkTOAnmd8Y svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-4VdXkOKkTOAnmd8Y p{margin:0;}#mermaid-svg-4VdXkOKkTOAnmd8Y .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-4VdXkOKkTOAnmd8Y .cluster-label text{fill:#333;}#mermaid-svg-4VdXkOKkTOAnmd8Y .cluster-label span{color:#333;}#mermaid-svg-4VdXkOKkTOAnmd8Y .cluster-label span p{background-color:transparent;}#mermaid-svg-4VdXkOKkTOAnmd8Y .label text,#mermaid-svg-4VdXkOKkTOAnmd8Y span{fill:#333;color:#333;}#mermaid-svg-4VdXkOKkTOAnmd8Y .node rect,#mermaid-svg-4VdXkOKkTOAnmd8Y .node circle,#mermaid-svg-4VdXkOKkTOAnmd8Y .node ellipse,#mermaid-svg-4VdXkOKkTOAnmd8Y .node polygon,#mermaid-svg-4VdXkOKkTOAnmd8Y .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-4VdXkOKkTOAnmd8Y .rough-node .label text,#mermaid-svg-4VdXkOKkTOAnmd8Y .node .label text,#mermaid-svg-4VdXkOKkTOAnmd8Y .image-shape .label,#mermaid-svg-4VdXkOKkTOAnmd8Y .icon-shape .label{text-anchor:middle;}#mermaid-svg-4VdXkOKkTOAnmd8Y .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-4VdXkOKkTOAnmd8Y .rough-node .label,#mermaid-svg-4VdXkOKkTOAnmd8Y .node .label,#mermaid-svg-4VdXkOKkTOAnmd8Y .image-shape .label,#mermaid-svg-4VdXkOKkTOAnmd8Y .icon-shape .label{text-align:center;}#mermaid-svg-4VdXkOKkTOAnmd8Y .node.clickable{cursor:pointer;}#mermaid-svg-4VdXkOKkTOAnmd8Y .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-4VdXkOKkTOAnmd8Y .arrowheadPath{fill:#333333;}#mermaid-svg-4VdXkOKkTOAnmd8Y .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-4VdXkOKkTOAnmd8Y .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-4VdXkOKkTOAnmd8Y .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-4VdXkOKkTOAnmd8Y .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-4VdXkOKkTOAnmd8Y .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-4VdXkOKkTOAnmd8Y .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-4VdXkOKkTOAnmd8Y .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-4VdXkOKkTOAnmd8Y .cluster text{fill:#333;}#mermaid-svg-4VdXkOKkTOAnmd8Y .cluster span{color:#333;}#mermaid-svg-4VdXkOKkTOAnmd8Y div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-4VdXkOKkTOAnmd8Y .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-4VdXkOKkTOAnmd8Y rect.text{fill:none;stroke-width:0;}#mermaid-svg-4VdXkOKkTOAnmd8Y .icon-shape,#mermaid-svg-4VdXkOKkTOAnmd8Y .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-4VdXkOKkTOAnmd8Y .icon-shape p,#mermaid-svg-4VdXkOKkTOAnmd8Y .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-4VdXkOKkTOAnmd8Y .icon-shape .label rect,#mermaid-svg-4VdXkOKkTOAnmd8Y .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-4VdXkOKkTOAnmd8Y .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-4VdXkOKkTOAnmd8Y .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-4VdXkOKkTOAnmd8Y :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

差分: diff[i]=a[i]-a[i-1]

前缀和: preSum[i]=Σdiff[0..i-1]

差分: diff[i]=preSum[i]-preSum[i-1]

前缀和

原数组 a

差分数组 diff

前缀和数组 preSum

二阶差分

面试关键：差分是"标记"，前缀和是"还原"。差分只改两个位置做标记，前缀和把标记扩散到整个数组。

四、二维前缀和

4.1 定义

给定矩阵 a[m][n]，前缀和 preSum[i][j] 表示左上角 (0,0) 到 (i-1,j-1) 的子矩阵之和：

preSum[i][j] = 以(0,0)为左上角、(i-1,j-1)为右下角的子矩阵元素之和

4.2 容斥原理推导

如何求 preSum[i][j]？ 用容斥原理（包含-排除）：

#mermaid-svg-R4J8UKZpIXK9EXkl{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-R4J8UKZpIXK9EXkl .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-R4J8UKZpIXK9EXkl .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-R4J8UKZpIXK9EXkl .error-icon{fill:#552222;}#mermaid-svg-R4J8UKZpIXK9EXkl .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-R4J8UKZpIXK9EXkl .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-R4J8UKZpIXK9EXkl .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-R4J8UKZpIXK9EXkl .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-R4J8UKZpIXK9EXkl .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-R4J8UKZpIXK9EXkl .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-R4J8UKZpIXK9EXkl .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-R4J8UKZpIXK9EXkl .marker{fill:#333333;stroke:#333333;}#mermaid-svg-R4J8UKZpIXK9EXkl .marker.cross{stroke:#333333;}#mermaid-svg-R4J8UKZpIXK9EXkl svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-R4J8UKZpIXK9EXkl p{margin:0;}#mermaid-svg-R4J8UKZpIXK9EXkl .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-R4J8UKZpIXK9EXkl .cluster-label text{fill:#333;}#mermaid-svg-R4J8UKZpIXK9EXkl .cluster-label span{color:#333;}#mermaid-svg-R4J8UKZpIXK9EXkl .cluster-label span p{background-color:transparent;}#mermaid-svg-R4J8UKZpIXK9EXkl .label text,#mermaid-svg-R4J8UKZpIXK9EXkl span{fill:#333;color:#333;}#mermaid-svg-R4J8UKZpIXK9EXkl .node rect,#mermaid-svg-R4J8UKZpIXK9EXkl .node circle,#mermaid-svg-R4J8UKZpIXK9EXkl .node ellipse,#mermaid-svg-R4J8UKZpIXK9EXkl .node polygon,#mermaid-svg-R4J8UKZpIXK9EXkl .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-R4J8UKZpIXK9EXkl .rough-node .label text,#mermaid-svg-R4J8UKZpIXK9EXkl .node .label text,#mermaid-svg-R4J8UKZpIXK9EXkl .image-shape .label,#mermaid-svg-R4J8UKZpIXK9EXkl .icon-shape .label{text-anchor:middle;}#mermaid-svg-R4J8UKZpIXK9EXkl .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-R4J8UKZpIXK9EXkl .rough-node .label,#mermaid-svg-R4J8UKZpIXK9EXkl .node .label,#mermaid-svg-R4J8UKZpIXK9EXkl .image-shape .label,#mermaid-svg-R4J8UKZpIXK9EXkl .icon-shape .label{text-align:center;}#mermaid-svg-R4J8UKZpIXK9EXkl .node.clickable{cursor:pointer;}#mermaid-svg-R4J8UKZpIXK9EXkl .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-R4J8UKZpIXK9EXkl .arrowheadPath{fill:#333333;}#mermaid-svg-R4J8UKZpIXK9EXkl .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-R4J8UKZpIXK9EXkl .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-R4J8UKZpIXK9EXkl .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-R4J8UKZpIXK9EXkl .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-R4J8UKZpIXK9EXkl .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-R4J8UKZpIXK9EXkl .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-R4J8UKZpIXK9EXkl .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-R4J8UKZpIXK9EXkl .cluster text{fill:#333;}#mermaid-svg-R4J8UKZpIXK9EXkl .cluster span{color:#333;}#mermaid-svg-R4J8UKZpIXK9EXkl div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-R4J8UKZpIXK9EXkl .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-R4J8UKZpIXK9EXkl rect.text{fill:none;stroke-width:0;}#mermaid-svg-R4J8UKZpIXK9EXkl .icon-shape,#mermaid-svg-R4J8UKZpIXK9EXkl .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-R4J8UKZpIXK9EXkl .icon-shape p,#mermaid-svg-R4J8UKZpIXK9EXkl .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-R4J8UKZpIXK9EXkl .icon-shape .label rect,#mermaid-svg-R4J8UKZpIXK9EXkl .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-R4J8UKZpIXK9EXkl .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-R4J8UKZpIXK9EXkl .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-R4J8UKZpIXK9EXkl :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

求 preSum[i][j]

整个矩形 S(i,j)

减去上方 S(i-1,j)

减去左方 S(i,j-1)

加上左上 S(i-1,j-1)（被减了两次，加回来）

preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] – preSum[i-1][j-1] + a[i-1][j-1]

图解：

┌──────────────────────┐
│ S(i-1,j-1) │ S(i-1,j) = S(i-1,j-1) + 上方横条
├──────────────────────┤ S(i,j-1) = S(i-1,j-1) + 左方竖条
│ 左方竖条 │ S(i,j) = S(i-1,j) + S(i,j-1) – S(i-1,j-1) + a[i-1][j-1]
│ │
└──────────────────────┘

4.3 O(1) 子矩阵求和

给定左上角 (r1,c1) 和右下角 (r2,c2)，求子矩阵之和：

sum = preSum[r2+1][c2+1] – preSum[r1][c2+1] – preSum[r2+1][c1] + preSum[r1][c1]

#mermaid-svg-EGi44KaI2K6kePvO{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-EGi44KaI2K6kePvO .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-EGi44KaI2K6kePvO .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-EGi44KaI2K6kePvO .error-icon{fill:#552222;}#mermaid-svg-EGi44KaI2K6kePvO .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-EGi44KaI2K6kePvO .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-EGi44KaI2K6kePvO .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-EGi44KaI2K6kePvO .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-EGi44KaI2K6kePvO .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-EGi44KaI2K6kePvO .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-EGi44KaI2K6kePvO .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-EGi44KaI2K6kePvO .marker{fill:#333333;stroke:#333333;}#mermaid-svg-EGi44KaI2K6kePvO .marker.cross{stroke:#333333;}#mermaid-svg-EGi44KaI2K6kePvO svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-EGi44KaI2K6kePvO p{margin:0;}#mermaid-svg-EGi44KaI2K6kePvO .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-EGi44KaI2K6kePvO .cluster-label text{fill:#333;}#mermaid-svg-EGi44KaI2K6kePvO .cluster-label span{color:#333;}#mermaid-svg-EGi44KaI2K6kePvO .cluster-label span p{background-color:transparent;}#mermaid-svg-EGi44KaI2K6kePvO .label text,#mermaid-svg-EGi44KaI2K6kePvO span{fill:#333;color:#333;}#mermaid-svg-EGi44KaI2K6kePvO .node rect,#mermaid-svg-EGi44KaI2K6kePvO .node circle,#mermaid-svg-EGi44KaI2K6kePvO .node ellipse,#mermaid-svg-EGi44KaI2K6kePvO .node polygon,#mermaid-svg-EGi44KaI2K6kePvO .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-EGi44KaI2K6kePvO .rough-node .label text,#mermaid-svg-EGi44KaI2K6kePvO .node .label text,#mermaid-svg-EGi44KaI2K6kePvO .image-shape .label,#mermaid-svg-EGi44KaI2K6kePvO .icon-shape .label{text-anchor:middle;}#mermaid-svg-EGi44KaI2K6kePvO .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-EGi44KaI2K6kePvO .rough-node .label,#mermaid-svg-EGi44KaI2K6kePvO .node .label,#mermaid-svg-EGi44KaI2K6kePvO .image-shape .label,#mermaid-svg-EGi44KaI2K6kePvO .icon-shape .label{text-align:center;}#mermaid-svg-EGi44KaI2K6kePvO .node.clickable{cursor:pointer;}#mermaid-svg-EGi44KaI2K6kePvO .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-EGi44KaI2K6kePvO .arrowheadPath{fill:#333333;}#mermaid-svg-EGi44KaI2K6kePvO .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-EGi44KaI2K6kePvO .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-EGi44KaI2K6kePvO .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-EGi44KaI2K6kePvO .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-EGi44KaI2K6kePvO .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-EGi44KaI2K6kePvO .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-EGi44KaI2K6kePvO .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-EGi44KaI2K6kePvO .cluster text{fill:#333;}#mermaid-svg-EGi44KaI2K6kePvO .cluster span{color:#333;}#mermaid-svg-EGi44KaI2K6kePvO div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-EGi44KaI2K6kePvO .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-EGi44KaI2K6kePvO rect.text{fill:none;stroke-width:0;}#mermaid-svg-EGi44KaI2K6kePvO .icon-shape,#mermaid-svg-EGi44KaI2K6kePvO .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-EGi44KaI2K6kePvO .icon-shape p,#mermaid-svg-EGi44KaI2K6kePvO .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-EGi44KaI2K6kePvO .icon-shape .label rect,#mermaid-svg-EGi44KaI2K6kePvO .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-EGi44KaI2K6kePvO .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-EGi44KaI2K6kePvO .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-EGi44KaI2K6kePvO :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

子矩阵求和

preSum[r2+1][c2+1]整个大矩形

减 preSum[r1][c2+1]上方矩形

减 preSum[r2+1][c1]左方矩形

加 preSum[r1][c1]左上矩形（被减两次）

4.4 完整代码

// 二维前缀和
class PrefixSum2D {
private int[][] preSum;

// O(mn) 预处理
public PrefixSum2D(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
preSum = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
preSum[i][j] = preSum[i – 1][j] + preSum[i][j – 1]
– preSum[i – 1][j – 1] + matrix[i – 1][j – 1];
}
}
}

// O(1) 查询子矩阵 (r1,c1) 到 (r2,c2) 的和
public int sumRegion(int r1, int c1, int r2, int c2) {
return preSum[r2 + 1][c2 + 1] – preSum[r1][c2 + 1]
– preSum[r2 + 1][c1] + preSum[r1][c1];
}
}

4.5 逐帧图解

原矩阵: 前缀和矩阵:
┌───┬───┬───┐ ┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ │ 0 │ 0 │ 0 │ 0 │
├───┼───┼───┤ ├───┼───┼───┼───┤
│ 4 │ 5 │ 6 │ │ 0 │ 1 │ 3 │ 6 │
├───┼───┼───┤ ├───┼───┼───┼───┤
│ 7 │ 8 │ 9 │ │ 0 │ 5 │12 │21 │
└───┴───┴───┘ ├───┼───┼───┼───┤
│ 0 │12 │27 │45 │
└───┴───┴───┴───┘

查询 (1,1) 到 (2,2) 的子矩阵和:
= preSum[3][3] – preSum[1][3] – preSum[3][1] + preSum[1][1]
= 45 – 6 – 12 + 1 = 28
验证: 5+6+8+9 = 28 ✅

五、二维差分

5.1 核心公式：O(1) 子矩阵修改

对子矩阵 (r1,c1) 到 (r2,c2) 每个元素加 val：

diff[r1][c1] += val;
diff[r1][c2 + 1] -= val;
diff[r2 + 1][c1] -= val;
diff[r2 + 1][c2 + 1] += val;

为什么改4个位置？ 和一维差分同理，只是二维需要4个角来"圈定"修改范围：

#mermaid-svg-V2yqDyoYUFNcSiK6{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-V2yqDyoYUFNcSiK6 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-V2yqDyoYUFNcSiK6 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-V2yqDyoYUFNcSiK6 .error-icon{fill:#552222;}#mermaid-svg-V2yqDyoYUFNcSiK6 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-V2yqDyoYUFNcSiK6 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-V2yqDyoYUFNcSiK6 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-V2yqDyoYUFNcSiK6 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-V2yqDyoYUFNcSiK6 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-V2yqDyoYUFNcSiK6 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-V2yqDyoYUFNcSiK6 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-V2yqDyoYUFNcSiK6 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-V2yqDyoYUFNcSiK6 .marker.cross{stroke:#333333;}#mermaid-svg-V2yqDyoYUFNcSiK6 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-V2yqDyoYUFNcSiK6 p{margin:0;}#mermaid-svg-V2yqDyoYUFNcSiK6 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-V2yqDyoYUFNcSiK6 .cluster-label text{fill:#333;}#mermaid-svg-V2yqDyoYUFNcSiK6 .cluster-label span{color:#333;}#mermaid-svg-V2yqDyoYUFNcSiK6 .cluster-label span p{background-color:transparent;}#mermaid-svg-V2yqDyoYUFNcSiK6 .label text,#mermaid-svg-V2yqDyoYUFNcSiK6 span{fill:#333;color:#333;}#mermaid-svg-V2yqDyoYUFNcSiK6 .node rect,#mermaid-svg-V2yqDyoYUFNcSiK6 .node circle,#mermaid-svg-V2yqDyoYUFNcSiK6 .node ellipse,#mermaid-svg-V2yqDyoYUFNcSiK6 .node polygon,#mermaid-svg-V2yqDyoYUFNcSiK6 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-V2yqDyoYUFNcSiK6 .rough-node .label text,#mermaid-svg-V2yqDyoYUFNcSiK6 .node .label text,#mermaid-svg-V2yqDyoYUFNcSiK6 .image-shape .label,#mermaid-svg-V2yqDyoYUFNcSiK6 .icon-shape .label{text-anchor:middle;}#mermaid-svg-V2yqDyoYUFNcSiK6 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-V2yqDyoYUFNcSiK6 .rough-node .label,#mermaid-svg-V2yqDyoYUFNcSiK6 .node .label,#mermaid-svg-V2yqDyoYUFNcSiK6 .image-shape .label,#mermaid-svg-V2yqDyoYUFNcSiK6 .icon-shape .label{text-align:center;}#mermaid-svg-V2yqDyoYUFNcSiK6 .node.clickable{cursor:pointer;}#mermaid-svg-V2yqDyoYUFNcSiK6 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-V2yqDyoYUFNcSiK6 .arrowheadPath{fill:#333333;}#mermaid-svg-V2yqDyoYUFNcSiK6 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-V2yqDyoYUFNcSiK6 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-V2yqDyoYUFNcSiK6 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-V2yqDyoYUFNcSiK6 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-V2yqDyoYUFNcSiK6 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-V2yqDyoYUFNcSiK6 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-V2yqDyoYUFNcSiK6 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-V2yqDyoYUFNcSiK6 .cluster text{fill:#333;}#mermaid-svg-V2yqDyoYUFNcSiK6 .cluster span{color:#333;}#mermaid-svg-V2yqDyoYUFNcSiK6 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-V2yqDyoYUFNcSiK6 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-V2yqDyoYUFNcSiK6 rect.text{fill:none;stroke-width:0;}#mermaid-svg-V2yqDyoYUFNcSiK6 .icon-shape,#mermaid-svg-V2yqDyoYUFNcSiK6 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-V2yqDyoYUFNcSiK6 .icon-shape p,#mermaid-svg-V2yqDyoYUFNcSiK6 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-V2yqDyoYUFNcSiK6 .icon-shape .label rect,#mermaid-svg-V2yqDyoYUFNcSiK6 .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-V2yqDyoYUFNcSiK6 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-V2yqDyoYUFNcSiK6 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-V2yqDyoYUFNcSiK6 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

效果

二维差分标记

diff[r1][c1] += val左上角：从这里开始+val

diff[r1][c2+1] -= val右上角：右边界外取消+val

diff[r2+1][c1] -= val左下角：下边界外取消+val

diff[r2+1][c2+1] += val右下角：右下外恢复+val（被减了两次）

目标区域: +val

右侧/下方: 被减回0

右下角: 被减两次加回0

5.2 完整代码

// 二维差分
class Difference2D {
private int[][] diff;
private int m, n;

public Difference2D(int[][] matrix) {
m = matrix.length;
n = matrix[0].length;
diff = new int[m + 2][n + 2]; // 多开2，避免边界判断
// 初始化：每个位置视为对单点做 +a[i][j] 的区间修改
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
increment(i, j, i, j, matrix[i][j]);
}
}
}

// O(1) 子矩阵 (r1,c1) 到 (r2,c2) 每个元素加 val
public void increment(int r1, int c1, int r2, int c2, int val) {
diff[r1 + 1][c1 + 1] += val;
diff[r1 + 1][c2 + 2] -= val;
diff[r2 + 2][c1 + 1] -= val;
diff[r2 + 2][c2 + 2] += val;
}

// O(mn) 还原矩阵
public int[][] result() {
int[][] res = new int[m][n];
// 对 diff 做二维前缀和
int[][] preSum = new int[m + 2][n + 2];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
preSum[i][j] = preSum[i – 1][j] + preSum[i][j – 1]
– preSum[i – 1][j – 1] + diff[i][j];
res[i – 1][j – 1] = preSum[i][j];
}
}
return res;
}
}

5.3 一维 vs 二维对比

规律：差分标记数 = 2^维度。一维2个，二维4个，三维8个。

六、前缀和的五大变形

6.1 变形一：前缀和 + 哈希（和为K的子数组）

已在上文2.4节讲解。核心：preSum[j] – preSum[i] = K → 找 preSum[j] – K 出现次数。

6.2 变形二：前缀积（乘积区间）

// 前缀积：区间 [l, r] 的乘积
class PrefixProduct {
private long[] preProd;
private long MOD = 1_000_000_007;

public PrefixProduct(int[] nums) {
int n = nums.length;
preProd = new long[n + 1];
preProd[0] = 1;
for (int i = 0; i < n; i++) {
preProd[i + 1] = preProd[i] * nums[i] % MOD;
}
}

// 区间 [l, r] 的乘积（模意义下）
// 需要 nums 中无0，或用逆元处理
public long productRange(int l, int r) {
return preProd[r + 1] * modInverse(preProd[l]) % MOD;
}
}

注意：含0的数组不能用前缀积，需要特殊处理（记录0的位置）。

6.3 变形三：前缀异或

// 前缀异或：区间 [l, r] 的异或结果
// preXor[i] = a[0] ^ a[1] ^ … ^ a[i-1]
// 区间 [l, r] 的异或 = preXor[r+1] ^ preXor[l]
class PrefixXor {
private int[] preXor;

public PrefixXor(int[] nums) {
int n = nums.length;
preXor = new int[n + 1];
for (int i = 0; i < n; i++) {
preXor[i + 1] = preXor[i] ^ nums[i];
}
}

public int xorRange(int l, int r) {
return preXor[r + 1] ^ preXor[l];
}
}

应用：LeetCode 1734（解码异或排列）、1738（找出第K大的异或坐标值）。

6.4 变形四：前缀和 + 单调栈

问题：求满足 sum[i..j] ≥ K 的最短子数组长度。

思路：前缀和 + 单调队列，维护递增的前缀和序列，O(n)。

6.5 变形五：差分数组 + 原地扫描

问题：航班预订统计（LeetCode 1109）。

// LeetCode 1109: 航班预订统计
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] diff = new int[n + 1];
for (int[] b : bookings) {
int first = b[0], last = b[1], seats = b[2];
diff[first – 1] += seats; // 航班编号从1开始
diff[last] -= seats;
}
int[] res = new int[n];
res[0] = diff[0];
for (int i = 1; i < n; i++) {
res[i] = res[i – 1] + diff[i];
}
return res;
}

七、LeetCode 精选实战

🟢 入门题

LeetCode 724 代码：

public int pivotIndex(int[] nums) {
int total = 0;
for (int num : nums) total += num;
int leftSum = 0;
for (int i = 0; i < nums.length; i++) {
if (leftSum == total – leftSum – nums[i]) return i;
leftSum += nums[i];
}
return –1;
}

🟡 进阶题

LeetCode 1094 拼车代码：

public boolean carPooling(int[][] trips, int capacity) {
int[] diff = new int[1001]; // 最多1000个位置
for (int[] t : trips) {
int num = t[0], from = t[1], to = t[2];
diff[from] += num;
diff[to] -= num; // to下车，不在to站占座
}
int load = 0;
for (int i = 0; i < 1001; i++) {
load += diff[i];
if (load > capacity) return false;
}
return true;
}

🔴 困难题

LeetCode 1314 矩阵区域和代码：

public int[][] matrixBlockSum(int[][] mat, int k) {
int m = mat.length, n = mat[0].length;
PrefixSum2D ps = new PrefixSum2D(mat);
int[][] res = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int r1 = Math.max(0, i – k), c1 = Math.max(0, j – k);
int r2 = Math.min(m – 1, i + k), c2 = Math.min(n – 1, j + k);
res[i][j] = ps.sumRegion(r1, c1, r2, c2);
}
}
return res;
}

八、面试速查表

九、总结全景图

#mermaid-svg-mTf5ZD0uh5FPyCwG{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-mTf5ZD0uh5FPyCwG .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-mTf5ZD0uh5FPyCwG .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-mTf5ZD0uh5FPyCwG .error-icon{fill:#552222;}#mermaid-svg-mTf5ZD0uh5FPyCwG .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-mTf5ZD0uh5FPyCwG .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-mTf5ZD0uh5FPyCwG .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-mTf5ZD0uh5FPyCwG .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-mTf5ZD0uh5FPyCwG .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-mTf5ZD0uh5FPyCwG .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-mTf5ZD0uh5FPyCwG .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-mTf5ZD0uh5FPyCwG .marker{fill:#333333;stroke:#333333;}#mermaid-svg-mTf5ZD0uh5FPyCwG .marker.cross{stroke:#333333;}#mermaid-svg-mTf5ZD0uh5FPyCwG svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-mTf5ZD0uh5FPyCwG p{margin:0;}#mermaid-svg-mTf5ZD0uh5FPyCwG .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-mTf5ZD0uh5FPyCwG .cluster-label text{fill:#333;}#mermaid-svg-mTf5ZD0uh5FPyCwG .cluster-label span{color:#333;}#mermaid-svg-mTf5ZD0uh5FPyCwG .cluster-label span p{background-color:transparent;}#mermaid-svg-mTf5ZD0uh5FPyCwG .label text,#mermaid-svg-mTf5ZD0uh5FPyCwG span{fill:#333;color:#333;}#mermaid-svg-mTf5ZD0uh5FPyCwG .node rect,#mermaid-svg-mTf5ZD0uh5FPyCwG .node circle,#mermaid-svg-mTf5ZD0uh5FPyCwG .node ellipse,#mermaid-svg-mTf5ZD0uh5FPyCwG .node polygon,#mermaid-svg-mTf5ZD0uh5FPyCwG .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-mTf5ZD0uh5FPyCwG .rough-node .label text,#mermaid-svg-mTf5ZD0uh5FPyCwG .node .label text,#mermaid-svg-mTf5ZD0uh5FPyCwG .image-shape .label,#mermaid-svg-mTf5ZD0uh5FPyCwG .icon-shape .label{text-anchor:middle;}#mermaid-svg-mTf5ZD0uh5FPyCwG .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-mTf5ZD0uh5FPyCwG .rough-node .label,#mermaid-svg-mTf5ZD0uh5FPyCwG .node .label,#mermaid-svg-mTf5ZD0uh5FPyCwG .image-shape .label,#mermaid-svg-mTf5ZD0uh5FPyCwG .icon-shape .label{text-align:center;}#mermaid-svg-mTf5ZD0uh5FPyCwG .node.clickable{cursor:pointer;}#mermaid-svg-mTf5ZD0uh5FPyCwG .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-mTf5ZD0uh5FPyCwG .arrowheadPath{fill:#333333;}#mermaid-svg-mTf5ZD0uh5FPyCwG .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-mTf5ZD0uh5FPyCwG .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-mTf5ZD0uh5FPyCwG .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-mTf5ZD0uh5FPyCwG .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-mTf5ZD0uh5FPyCwG .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-mTf5ZD0uh5FPyCwG .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-mTf5ZD0uh5FPyCwG .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-mTf5ZD0uh5FPyCwG .cluster text{fill:#333;}#mermaid-svg-mTf5ZD0uh5FPyCwG .cluster span{color:#333;}#mermaid-svg-mTf5ZD0uh5FPyCwG div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-mTf5ZD0uh5FPyCwG .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-mTf5ZD0uh5FPyCwG rect.text{fill:none;stroke-width:0;}#mermaid-svg-mTf5ZD0uh5FPyCwG .icon-shape,#mermaid-svg-mTf5ZD0uh5FPyCwG .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-mTf5ZD0uh5FPyCwG .icon-shape p,#mermaid-svg-mTf5ZD0uh5FPyCwG .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-mTf5ZD0uh5FPyCwG .icon-shape .label rect,#mermaid-svg-mTf5ZD0uh5FPyCwG .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-mTf5ZD0uh5FPyCwG .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-mTf5ZD0uh5FPyCwG .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-mTf5ZD0uh5FPyCwG :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

前缀和与差分

一维

二维

变形

前缀和: O1区间求和

差分: O1区间修改

互逆: 差分标记→前缀和还原

前缀和: 容斥原理4项

差分: 4角标记

规律: 2^维度个标记

前缀和+哈希: 和为K

前缀积: 乘积区间

前缀异或: 异或区间

差分+扫描: 航班/拼车

核心心法

前缀和: 预处理换查询

差分: 标记换修改

互逆: 差分是拆 前缀和是积

一句话带走：前缀和与差分是互逆操作对——前缀和是"积"（累加），差分是"拆"（相减）。前缀和用 O(n) 预处理换 O(1) 区间求和，差分用 O(1) 标记换 O(n) 还原区间修改。二维扩展用容斥原理，差分标记数 = 2^维度。前缀和+哈希解决"和为K的子数组"，差分+扫描解决"航班预订/拼车"类问题。核心心法：预处理换查询，标记换修改，差分是拆前缀和是积。