Prefix Sum

Key Signals & Indicators

• Requires multiple range sum queries on an array
• Computing subarrays that sum to target
• Prefix or suffix cumulative values are helpful

// C++ Prefix Sum Template
#include <vector>

class RangeSumQuery {
    std::vector<int> prefix;
public:
    RangeSumQuery(const std::vector<int>& arr) {
        prefix.resize(arr.size() + 1, 0);
        for (size_t i = 0; i < arr.size(); ++i) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
    }
    
    int querySum(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
};