📊 差分数组算法笔记

🎯 问题背景

在处理数组的区间修改问题时，如果直接使用暴力方法，可能会因为时间复杂度太高而导致超时⏰。差分数组是一种高效处理区间修改问题的数据结构，就像变魔术一样神奇！✨

💥 暴力方法的问题

🐌 暴力方法实现

#include<bits/stdc++.h>
using namespace std;
int a[1000010];

int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    
    int x, y, z;
    while(k--){
        cin >> x >> y >> z;
        // 🚫 暴力方法：对区间内每个元素逐个修改
        // 这就像一个人一个人地发糖果，太慢了！
        for(int i = x; i <= y; i++){
            a[i] += z;
        }
    }
    
    for(int i = 1; i <= n; i++){
        cout << a[i] << " ";
    }
    return 0;
}

📈 暴力方法的时间复杂度分析

数据样例演示：

n = 1000000, k = 1000000
暴力方法：1000000 × 1000000 = 1,000,000,000,000 次操作 ❌
差分数组：1000000 + 1000000 = 2,000,000 次操作 ✅

当n和k都很大时，暴力方法就像让一个人数完整个沙滩的沙子🏖️，而差分数组就像用机器快速扫描！

🚀 差分数组优化

💡 差分数组核心思想

差分数组b[i]定义为：b[i] = a[i] - a[i-1]

通过维护差分数组，可以将区间修改操作转化为两个单点修改操作，就像用杠杆撬动地球一样省力！🎯

🛠️ 差分数组实现

#include<bits/stdc++.h>
using namespace std;
int a[1000010], b[1000010];

int main(){
    // 输入n个数字，对n个数字进行k次修改
    // 每次修改是对区间[x,y]之间的数字增加z 
    int n, k;
    cin >> n >> k;
    
    // 输入原始数组并构建差分数组
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        b[i] = a[i] - a[i-1];  // 🏗️ 构建差分数组
    }
    
    int x, y, z;
    while(k--){
        cin >> x >> y >> z;
        
        // 🎯 差分数组的核心操作 - 就像开关控制一样精准！
        b[x] += z;      // ✅ 区间开始处打开"增加阀门"
        b[y+1] -= z;    // ✅ 区间结束后关闭"增加阀门"
    } 
    
    // 通过差分数组还原最终数组
    for(int i = 1; i <= n; i++){
        a[i] = a[i-1] + b[i];  // 🔄 前缀和还原
    }
    
    // 输出结果
    for(int i = 1; i <= n; i++){
        cout << a[i] << " ";
    }
    return 0;
}

🎨 差分数组原理详解

1. 📐 差分数组定义

原始数组: a = [a₁, a₂, a₃, ..., aₙ]
差分数组: b = [b₁, b₂, b₃, ..., bₙ]
其中: bᵢ = aᵢ - aᵢ₋₁

2. 🎪 区间修改原理演示

例子： 数组 [1, 2, 3, 4, 5]，对区间 [2, 4] 增加 3

原始数组:    [1,  2,  3,  4,  5]
差分数组:    [1,  1,  1,  1,  1]

修改操作: b[2] += 3, b[5] -= 3

修改后差分: [1,  4,  1,  1, -2]

还原数组:
a₁ = 1
a₂ = 1 + 4 = 5
a₃ = 5 + 1 = 6
a₄ = 6 + 1 = 7
a₅ = 7 - 2 = 5

最终结果: [1, 5, 6, 7, 5] 🎉

3. 🔄 前缀和还原过程可视化

差分数组: [b₁, b₂, b₃, b₄, b₅]
         ↓   ↓   ↓   ↓   ↓
原始数组: [b₁, b₁+b₂, b₁+b₂+b₃, b₁+b₂+b₃+b₄, b₁+b₂+b₃+b₄+b₅]

⏱️ 时间复杂度对比

性能提升对比：

当 n=10⁶, k=10⁶ 时：
暴力方法：10¹² 次操作 ≈ 16分钟 ⏰
差分数组：2×10⁶ 次操作 ≈ 0.003秒 ⚡
速度提升：500,000倍！ 🤯

🎯 应用场景

差分数组特别适用于以下场景：📋

1. 🎮 多次区间加减操作 - 就像游戏中的区域效果
2. 📊 区间修改后需要查询最终结果 - 批量处理数据
3. 🏆 时间限制严格的编程竞赛题目 - ACM/ICPC等比赛必备技能

⚠️ 注意事项

1. 🎯 数组下标从1开始，避免边界问题
2. 🚧 注意b[y+1]可能越界，需要保证数组大小足够
3. 📦 差分数组主要用于离线处理，不适合需要频繁查询中间结果的场景

🎓 学习建议

1. 🧩 先理解概念：把差分数组想象成"变化量的记录本" 📒
2. 🔢 手动模拟：用纸笔计算小例子，加深理解 ✏️
3. 💻 多写代码：实现几个变种题目，熟能生巧 🏋️
4. 🎯 识别模式：遇到"区间修改"关键词，立即想到差分数组 💡

通过使用差分数组，我们可以将区间修改问题的时间复杂度从O(n)优化到O(1)，在处理大规模数据时避免超时问题。就像从步行🚶升级到乘坐火箭🚀一样的效果！

记住：聪明的算法选择 > 盲目的暴力求解 🧠 > 💪

Happy Coding! 🎉👨‍💻👩‍💻