segment_tree.cpp File Reference

A data structure to quickly do operations on ranges: the Segment Tree algorithm implementation. More...

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

Include dependency graph for segment_tree.cpp:

Classes
class	data_structures::SegmentTree< T >
	class representation of the segment tree More...

Namespaces
namespace	data_structures
	for IO operations

Functions
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

A data structure to quickly do operations on ranges: the Segment Tree algorithm implementation.

Implementation of the segment tree data structre

Can do point updates (updates the value of some position) and range queries, where it gives the value of some associative opperation done on a range

Both of these operations take O(log N) time

Author

Nishant Chatterjee

Function Documentation

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:

test()

static void test ( )

static

Self-test implementations.

Returns

void

                   {
    data_structures::SegmentTree<int> t(5);
    t.update(1, 1);
    t.update(2, 2);
    t.update(3, 3);
    t.update(4, 4);
    t.update(5, 5);
    assert(t.range_comb(1, 3) == 6); // 1 + 2 + 3 = 6
    t.update(1, 3);
    assert(t.range_comb(1, 3) == 8); // 3 + 2 + 3 = 8
 
    std::cout << "All tests have successfully passed!\n";
}

Here is the call graph for this function: