Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
Prefix Sum Array data structure implementation. More...
#include <cassert>
#include <iostream>
#include <vector>
Namespaces | |
namespace | range_queries |
for std::vector | |
namespace | prefix_sum_array |
Range sum queries using prefix-sum-array. | |
Functions | |
void | range_queries::prefix_sum_array::build (std::vector< int64_t > original_array) |
function that builds the PSA | |
int64_t | range_queries::prefix_sum_array::query (int64_t beg, int64_t end) |
query function | |
static void | test () |
Self-test implementations. | |
int | main () |
Main function. | |
Variables | |
std::vector< int64_t > | range_queries::prefix_sum_array::PSA (1, 0) |
Prefix Sum Array data structure implementation.
Prefix Sum Array is a data structure, that allows answering sum in some range queries. It can answer most sum range queries in O(1), with a build time complexity of O(N). But it hasn't an update querie.
void range_queries::prefix_sum_array::build | ( | std::vector< int64_t > | original_array | ) |
function that builds the PSA
original_array | original array of values |
int main | ( | void | ) |
int64_t range_queries::prefix_sum_array::query | ( | int64_t | beg, |
int64_t | end ) |
|
static |
Self-test implementations.