Skip to content
A C++ example of a segment tree for Range Minimum Query (RMQ). Tutorial can be found (eventually) at www.srcmake.com/home/segment-tree
C++ Makefile
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
src
.gitignore
LICENSE Added LICENSE Sep 2, 2019
README.md [README] Updated site url. Sep 15, 2019
makefile

README.md

Segment Trees

Segment Trees are data structures that let you easily find the minimum, maximum, or sum over a given subrange of a larger range.

I've created a tutorial explaining how segment trees work and the process of building/updating/querying one here.

This repository contains a C++ class that implements a segment tree for a minimum (Range Minimum Query) example.

Please note that I've intentionally left the code unoptimized for the reader to make better, as this code is meant to be easily understandable to the viewer, not necessarily the most efficient implementation.

File Structure

The segment tree code exists as a class in segment-tree.hpp. The class is encapsulated within a namespace of srcmake to avoid any collisions with another library's segment tree.

(I've also bundled the header file with the cpp file because realistically when using a segment tree in an algorithm competition, we just want to be able to copy and paste the entire thing without worrying about eloquent file structures.)

main.cpp has a single main function that calls the segment-tree class with some example queries.

Deployment

The makefile will compile the project with C++14 (the version was chosen arbitrarily, we're not really using any special language features).

On Linux/Mac, as long as you have GCC, the following command will compile and run the project.

make

LICENSE

This code is licensed under the MIT License.

You can’t perform that action at this time.