There are a lot of tutorials online showing developers how to write various data structures. There are not a lot of tutorials showing how, when, or whether to use them. In this series, I cover practical uses and implications of data structures in frontend applications. In this edition, we’ll review the Segment Tree.
A Segment Tree is a data structure that can be used to perform range queries and range updates. It is a height-balanced binary tree, usually built on top of an Array. Segment Trees can be used to solve Range Min/Max & Sum Queries and Range Update Queries in O(log n) time.
The Segment Tree works like other tree data structures. It creates query paths that limit the amount of processing required to return data. Each intermediate node of the tree represents a segment of the data set. The root node contains the sum of all numbers in the tree. Its children contain the sums of all the numbers in their respective ranges, and so on down the tree to leaf nodes.
Segment Trees are useful whenever you’re frequently working with ranges of numerical data. The most common use cases for Segment Trees are:
This doesn’t mean that using Segment Trees is limited to working with numbers. You can work with Segment Trees, for example, to find all the intervals (or ranges) that match a specific criteria. The classic example of this is the Brackets Problem.
vue cli. Here’s what it looks like:
fakerto generate a set of 10,000 bids.
Here’s the base code for the grid. Note, it doesn’t use any specific collection data structure. Implementation details for the Segment Tree and the Array, follow.
Here’s the Array-based code:
Here’s the Segment Tree-based code:
I tested three things for performance:
All tests were conducted using Chrome 65.x. The range of data used for each query was 1–3000.
Loading data items
Segment Trees initialize in O(n*log(n)) time. To give you a practical sense of this, it took an average of 2.6 seconds to add 10,000 items to the Segment Tree.
In most cases, on the frontend, data like that in the BidGrid will be provided to an application from a backend API in an Array. In this case, we already have the data in our data structure; there’s no need to discuss load time.
Range Minimum Query:
This query finds the smallest value in the range.
The Segment Tree-based query was blisteringly faster than the Array-based query. It was 2,250% faster.
This query sums all the values in the range.
Again, the Segment Tree was amazing. It was 2,140% faster than the Array method.
Note: In the test above, the initial sum query took around 1 second. All subsequent sum queries were approximately 0.25 seconds — even when the query range was changed.
Using Segment Tree for this task was easier than using an Array. There was no need to create
reduce methods to get the desired result. The Segment Tree had all the query methods built in.
The code snippet below contrasts the code required for Segment Tree and Array:
The Segment Tree is an amazing data structure when you have a search-heavy application that performs a lot of specific range queries on a data set (e.g., sum, min, and max queries). It can definitely make sense to use a Segment Tree in a frontend application, if the needs of the application call for it.
Using a Segment Tree instead of an Array may have some performance costs, such as: