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.
What is a 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.
When to use Segment Trees
Segment Trees are useful whenever you’re frequently working with ranges of numerical data. The most common use cases for Segment Trees are:
- Sum all elements in a range.
- Find the min or max value of elements in a range.
- Update all elements in a range.
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.
Using Segment Trees in a Frontend App
NOTE: Various JavaScript engines will implement the JavaScript spec. differently. Therefore, from environment to environment performance results may vary.
The most common way to represent Collections in JavaScript is with Arrays. To find out if it could make sense to use a Segment Tree in a Frontend app, let’s contrast using a Segment Tree and an Array for the same task. Here’s the criteria we’ll use to evaluate them:
- Performance (run time and load time)
- Ease of use, and readability
Setup
- I wrote a quick Bid Grid in Vue, using
vue cli. Here’s what it looks like:
- I couldn’t find a Segment Tree implementation in JavaScript that I liked. So, with a little help from the Algorithms book website, I rolled my own.
- I used
[faker](https://github.com/marak/Faker.js/)to generate a set of 10,000 bids.
Code
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:
Performance
I tested three things for performance:
- Loading the data items into the data structure.
- Searching the data structure for the min value in a range.
- Summing the values in a range.
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.
Range Sum: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.
Ease of Use
Using Segment Tree for this task was easier than using an Array. There was no need to create filter or 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:
Conclusion
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:
- Segment Tree Initialization. This is a one-time cost for each Segment Tree. Because of this, it is recommended that you defer the initialization of a Segment Tree until after the page has loaded.