prefix_sum_array.cpp

Go to the documentation of this file.

 
#include <cassert>   
#include <iostream>  
#include <vector>    

namespace range_queries {
namespace prefix_sum_array {
 
std::vector<int64_t> PSA{};

void build(const std::vector<int64_t>& original_array) {
    PSA.clear();
    PSA.push_back(0);
    for (std::size_t i = 1; i < original_array.size(); ++i) {
        PSA.push_back(PSA.back() + original_array[i]);
    }
}

int64_t query(int64_t beg, int64_t end) { return PSA[end] - PSA[beg - 1]; }
 
}  // namespace prefix_sum_array
}  // namespace range_queries

static void test() {
    std::vector<int64_t> values{0,  123, 0,  2,  -2, 5,
                                24, 0,   23, -1, -1};  // original array
 
    range_queries::prefix_sum_array::build(values);
    // queries are of the type: sum of the range [a, b] = psa[b] - psa[a-1]
 
    assert(range_queries::prefix_sum_array::query(1, 10) ==
           173);  // sum of the entire array
    assert(range_queries::prefix_sum_array::query(4, 6) ==
           27);  // the sum of the interval [4, 6]
    assert(range_queries::prefix_sum_array::query(5, 9) ==
           51);  // the sum of the interval [5, 9]
}

int main() {
    test();  // run self-test implementations
    return 0;
}