prefix_sum_array.cpp File Reference

Prefix Sum Array data structure implementation. More...

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

Include dependency graph for prefix_sum_array.cpp:

Go to the source code of this file.

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 (const 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 {}

Detailed Description

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.

• Running Time Complexity
  
• Build : O(N)
  
• Range Query : O(1)
  

  Author

  Paulo Vitor Lima Borges

Definition in file prefix_sum_array.cpp.

Function Documentation

build()

void range_queries::prefix_sum_array::build

(

const std::vector< int64_t > &

original_array

)

function that builds the PSA

Parameters

original_array

original array of values

Returns

void

Definition at line 41 of file prefix_sum_array.cpp.

                                                     {
    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]);
    }
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 82 of file prefix_sum_array.cpp.

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

query()

int64_t range_queries::prefix_sum_array::query	(	int64_t	beg,
		int64_t	end )

query function

Parameters

beg	begin of the interval to sum
end	end of the interval to sum

Returns

sum of the range [beg, end]

Definition at line 54 of file prefix_sum_array.cpp.

{ return PSA[end] - PSA[beg - 1]; }

test()

void test ( )

static

Self-test implementations.

Returns

void

Definition at line 63 of file prefix_sum_array.cpp.

                   {
    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]
}

Variable Documentation

PSA

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

Definition at line 34 of file prefix_sum_array.cpp.

{};