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:

Go to the source code of this file.

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

Definition in file segment_tree.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 130 of file segment_tree.cpp.

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

test()

static void test ( )

static

Self-test implementations.

Returns

void

Definition at line 112 of file segment_tree.cpp.

                   {
    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";
}