差分数组是通过构造辅助数组d（d[0]=a[0]，d[i]=a[i]−a[i−1]）将原数组区间增减操作从o(n)优化至o(1)的技巧：对a[l..r]加x仅需d[l]+=x、d[r+1]−=x（r+1
什么是差分数组，为什么用它
差分数组不是标准库容器，而是一种技巧：对原数组 a 构造新数组 d，使得 d[0] = a[0]，且对 i > 0 有 d[i] = a[i] - a[i-1]。它的核心价值在于——把区间加减操作从 O(n) 降为 O(1)。比如要给 a[l..r] 全部加 x，只需改两个位置：d[l] += x，若 r+1 则 <code>d[r+1] -= x。
注意：差分数组本身不直接反映原值，必须通过前缀和还原；它适合「多次区间修改 + 最终一次性查询」的场景，比如离线处理涂色、覆盖、计数类问题。
怎么求差分数组（C++ 实现）
假设你有一个 std::vector<int></int> 或裸数组 int a[n]，求差分数组 d 很简单：
std::vector<int> d(n); d[0] = a[0]; for (int i = 1; i <p>常见错误：</p><div class="aritcle_card flexRow artxards"> <div class="artcardd flexRow"> <a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架"><img src="https://img.php.cn/upload/skill/000/000/081/178988956499722.jpg" alt="C++ 算法竞赛自动化测试数据生成与校验框架" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a> <div class="aritcle_card_info flexColumn"> <a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="overflowclass">C++ 算法竞赛自动化测试数据生成与校验框架</a> <p class="overflowclass">根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。</p> </div> <a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span> </a> </div> </div> <ul> <li>忘记初始化 <code>d[0]</code>，误写成全用 <code>a[i] - a[i-1]</code> 导致越界访问 <code>a[-1]</code> </li> <li>用 <code>int d[n]</code> 在栈上分配但 <code>n</code> 是运行时变量（C++ 不支持 VLAs），应改用 <code>std::vector</code> 或 <code>new int[n]</code> </li> <li>对空数组未判空，<code>n == 0</code> 时直接访问 <code>a[0]</code> 崩溃</li> </ul> <h3>怎么从差分数组还原原数组</h3> <p>还原就是做前缀和：用 <code>d</code> 重建 <code>a</code>，顺序不能错。</p> <pre class="brush:php;toolbar:false;">std::vector<int> a(n); a[0] = d[0]; for (int i = 1; i <p>关键点：</p> <ul> <li>还原必须严格按索引递增顺序累加，不能并行或乱序</li> <li>如果中间某次修改只更新了 <code>d[l]</code> 和 <code>d[r+1]</code>，但没还原就去读 <code>a[i]</code>，结果是错的——差分数组本身不存「当前值」</li> <li>还原后 <code>a</code> 的每个元素都是最终结果，没有中间态；若需多次查询中间状态，得在每次修改后重新还原，或改用线段树等结构</li> </ul> <h3>差分数组的边界与性能陷阱</h3> <p>看似简单，实际容易栽在细节：</p> <ul> <li> <code>r+1</code> 越界：区间修改时写 <code>d[r+1] -= x</code> 必须检查 <code>r+1 ，否则写到堆外或踩内存</code> </li> <li>数据类型溢出：差分值可能比原值范围更大（比如 <code>a[i]</code> 是 <code>int</code>，但连续加减后 <code>d[i]</code> 累积超限），必要时用 <code>long long</code> </li> <li>还原不可逆：还原一次得到的是「所有已应用修改后的数组」，没法回退某次修改——差分数组只记录净变化，不保存操作历史</li> <li>不适用于单点高频查询：如果一边改一边查某个 <code>a[i]</code>，还原整个数组 O(n) 太重，此时应避免用差分，改用 Fenwick Tree 或线段树</li> </ul> <p>差分数组真正的难点不在写法，而在判断「此刻该不该用它」：改得多、查得少、允许离线，才值得引入这个间接层。</p></int>
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
