TheAlgorithms/C++
1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
prefix_sum_array.cpp
Go to the documentation of this file.
1
18
19
#include <cassert>
20
#include <iostream>
21
#include <vector>
22
27
namespace
range_queries
{
32
namespace
prefix_sum_array
{
33
34
std::vector<int64_t> PSA(1, 0);
35
41
void
build
(std::vector<int64_t> original_array) {
42
for
(
int
i = 1; i <= static_cast<int>(original_array.size()); i++) {
43
PSA.push_back(PSA[i - 1] + original_array[i]);
44
}
45
}
46
52
int64_t
query
(int64_t beg, int64_t end) {
return
PSA[end] - PSA[beg - 1]; }
53
54
}
// namespace prefix_sum_array
55
}
// namespace range_queries
56
61
static
void
test
() {
62
std::vector<int64_t> values{0, 123, 0, 2, -2, 5,
63
24, 0, 23, -1, -1};
// original array
64
65
range_queries::prefix_sum_array::build
(values);
66
// queries are of the type: sum of the range [a, b] = psa[b] - psa[a-1]
67
68
assert(
range_queries::prefix_sum_array::query
(1, 10) ==
69
173);
// sum of the entire array
70
assert(
range_queries::prefix_sum_array::query
(4, 6) ==
71
27);
// the sum of the interval [4, 6]
72
assert(
range_queries::prefix_sum_array::query
(5, 9) ==
73
51);
// the sum of the interval [5, 9]
74
}
75
80
int
main
() {
81
test
();
// run self-test implementations
82
return
0;
83
}
prefix_sum_array
Range sum queries using prefix-sum-array.
range_queries
for std::vector
Definition
fenwick_tree.cpp:28
range_queries::prefix_sum_array::query
int64_t query(int64_t beg, int64_t end)
query function
Definition
prefix_sum_array.cpp:52
test
static void test()
Self-test implementations.
Definition
prefix_sum_array.cpp:61
range_queries::prefix_sum_array::build
void build(std::vector< int64_t > original_array)
function that builds the PSA
Definition
prefix_sum_array.cpp:41
main
int main()
Main function.
Definition
prefix_sum_array.cpp:80
range_queries
prefix_sum_array.cpp
Generated by
1.13.2