Difference Array

Key Signals & Indicators

• Requires multiple range increment/update operations
• Queries only happen after all range additions complete
• Requires performance optimization over repeated linear loops

// C++ Difference Array Template
#include <vector>

class DifferenceArray {
    std::vector<int> diff;
public:
    DifferenceArray(int size) : diff(size + 1, 0) {}
    
    void update(int left, int right, int val) {
        diff[left] += val;
        diff[right + 1] -= val;
    }
    
    std::vector<int> reconstruct() {
        std::vector<int> result(diff.size() - 1);
        int sum = 0;
        for (size_t i = 0; i < result.size(); ++i) {
            sum += diff[i];
            result[i] = sum;
        }
        return result;
    }
};