一维动态差分（区修单查）

动态差分是差分数组的动态实现，通过树状数组维护差分数组，可以在 $\mathcal{O}(\log n)$ 的时间复杂度内完成区间修改和单点查询操作。

基本概念

动态差分的核心思想是：

使用树状数组维护差分数组
区间修改转化为差分数组的两点修改
单点查询通过前缀和实现
适用于区间修改和单点查询交替的场景

实现方式

动态差分的关键操作：

update：修改差分数组某个位置的值
query：查询差分数组的前缀和
rangeAdd：区间增加操作
pointQuery：单点查询

基本实现

c++
java
python

class DynamicDifference {
private:
    vector<int> tree;
    int n;
    
    int lowbit(int x) {
        return x & (-x);
    }
    
    void update(int idx, int val) {
        while (idx <= n) {
            tree[idx] += val;
            idx += lowbit(idx);
        }
    }
    
    int query(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= lowbit(idx);
        }
        return sum;
    }

public:
    DynamicDifference(int size) : n(size) {
        tree.resize(n + 1);
    }
    
    // 区间[left, right]增加val
    void rangeAdd(int left, int right, int val) {
        update(left + 1, val);
        update(right + 2, -val);
    }
    
    // 查询位置idx的值
    int pointQuery(int idx) {
        return query(idx + 1);
    }
};

class DynamicDifference {
    private int[] tree;
    private int n;
    
    public DynamicDifference(int size) {
        n = size;
        tree = new int[n + 1];
    }
    
    private int lowbit(int x) {
        return x & (-x);
    }
    
    private void update(int idx, int val) {
        while (idx <= n) {
            tree[idx] += val;
            idx += lowbit(idx);
        }
    }
    
    private int query(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= lowbit(idx);
        }
        return sum;
    }
    
    // 区间[left, right]增加val
    public void rangeAdd(int left, int right, int val) {
        update(left + 1, val);
        update(right + 2, -val);
    }
    
    // 查询位置idx的值
    public int pointQuery(int idx) {
        return query(idx + 1);
    }
}

class DynamicDifference:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (size + 1)
    
    def lowbit(self, x):
        return x & (-x)
    
    def update(self, idx, val):
        while idx <= self.n:
            self.tree[idx] += val
            idx += self.lowbit(idx)
    
    def query(self, idx):
        total = 0
        while idx > 0:
            total += self.tree[idx]
            idx -= self.lowbit(idx)
        return total
    
    # 区间[left, right]增加val
    def range_add(self, left, right, val):
        self.update(left + 1, val)
        self.update(right + 2, -val)
    
    # 查询位置idx的值
    def point_query(self, idx):
        return self.query(idx + 1)

应用场景

动态差分在很多问题中都有应用：

动态区间增减
实时流量统计
在线温度变化
动态人流量统计
实时区间修改

示例：区间加法

cpp
java
python

class Solution {
private:
    DynamicDifference* dd;
    
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        dd = new DynamicDifference(length);
        
        // 执行所有更新操作
        for (const auto& update : updates) {
            int start = update[0];
            int end = update[1];
            int val = update[2];
            dd->rangeAdd(start, end, val);
        }
        
        // 查询每个位置的值
        vector<int> result(length);
        for (int i = 0; i < length; i++) {
            result[i] = dd->pointQuery(i);
        }
        
        return result;
    }
};

class Solution {
    private DynamicDifference dd;
    
    public int[] getModifiedArray(int length, int[][] updates) {
        dd = new DynamicDifference(length);
        
        // 执行所有更新操作
        for (int[] update : updates) {
            int start = update[0];
            int end = update[1];
            int val = update[2];
            dd.rangeAdd(start, end, val);
        }
        
        // 查询每个位置的值
        int[] result = new int[length];
        for (int i = 0; i < length; i++) {
            result[i] = dd.pointQuery(i);
        }
        
        return result;
    }
}

class Solution:
    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
        dd = DynamicDifference(length)
        
        # 执行所有更新操作
        for start, end, val in updates:
            dd.range_add(start, end, val)
        
        # 查询每个位置的值
        result = []
        for i in range(length):
            result.append(dd.point_query(i))
        
        return result