Quick start

In this section we are going to demonstrate how to use segment_tree with some code examples. First, let’s include some headers:

#include <mdds/segment_tree.hpp>
#include <string>
#include <iostream>

The <mdds/segment_tree.hpp> header defines the mdds::segment_tree template class, and we need to include the <string> so that we can use std::string as its value type. We also need the <iostream> header to write some outputs. The next step is to define a type alias for the concrete type instance of segment_tree:

using tree_type = mdds::segment_tree<long, std::string>;

Here, we are using long as the key type and std::string as the value type. Let’s create an instance of this type and insert some segments with values:

tree_type tree;

tree.insert(0, 10, "A");
tree.insert(2, 15, "B");
tree.insert(-2, 5, "C");
tree.insert(5, 22, "D");
tree.insert(20, 35, "E");

We have created a new instance called tree, and inserted five segment values into it using the insert() method, which takes:

• start position of the segment,

• end position of the segment, and

• the value associated with the segment

as its arguments. As mentioned earlier, the start position of a segment is inclusive but the end position isn’t. Once all the segment data have been inserted, the next step is to build the tree by simply calling the build_tree() method:

tree.build_tree();

Building the tree is required before you can perform any queries. Now that the tree is built, let’s run some queries. But first we are going to define the following helper function:

void search_and_print(const tree_type& tree, long pos)
{
    auto results = tree.search(pos);

    std::cout << "--" << std::endl;
    std::cout << "search at " << pos << std::endl;
    std::cout << "number of results: " << results.size() << std::endl;

    for (const auto& [start, end, value] : results)
        std::cout << "range: [" << start << ":" << end << "); value: " << value << std::endl;
}

This helper function takes the segment tree instance and a search point, performs a search by calling search(), and iterates through and prints its results. The return value from search() is of type search_results, which provides the size() method to quickly find the total number of the results. It also allows you to iterate through the results through its begin() end() methods, or simply by plugging it into a range-based for loop as you see in this function.

With this help function in place, let’s find all the segments that contain 5 by calling:

search_and_print(tree, 5);

which will print the following output:

--
search at 5
number of results: 3
range: [2:15); value: B
range: [0:10); value: A
range: [5:22); value: D

It’s worth pointing out that the results here don’t include the “C” segment, which extends from -2 to 5, because the end point is not inclusive. Given a search point of x, For a segment to be included in the results, it must satisfy start <= x < end. On the other hand, the results do include the “D” segment because the start point is inclusive.

Let’s do another search, and this time let’s find all the segments that contain 0:

search_and_print(tree, 0);

This will print the following output:

--
search at 0
number of results: 2
range: [-2:5); value: C
range: [0:10); value: A

The results look just about right. As an aside, it is entirely safe to call search() with points that are below the minimum position or above the maximum position in the tree; you will simply get empty results in such cases.