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:

Namespaces
namespace	range_queries
	Algorithms and Data Structures that support range queries and updates.
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)

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

Function Documentation

build()

void range_queries::prefix_sum_array::build

(

std::vector< int64_t >

original_array

)

function that builds the PSA

Parameters

original_array

original array of values

Returns

void

                                              {
    for (int i = 1; i <= static_cast<int>(original_array.size()); i++) {
        PSA.push_back(PSA[i - 1] + original_array[i]);
    }
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function.

Returns

0 on exit

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

Here is the call graph for this function:

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]

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

test()

static void test ( )

static

Self-test implementations.

Returns

void

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