Practical Data Structures for Frontend Applications: When to use Segment Trees

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 , 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. height-balanced binary tree 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 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 When to use Segment Trees Segment Trees are useful whenever you’re working with ranges of numerical data. The most common use cases for Segment Trees are: frequently 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 . Here’s what it looks like: vue cli I couldn’t find a Segment Tree implementation in JavaScript that I liked. So, with a little help from the website, I . Algorithms book rolled my own I used to generate a set of 10,000 bids. [faker](https://github.com/marak/Faker.js/) 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. :This query finds the smallest value in the range. Range Minimum Query 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. Range Sum Again, the Segment Tree was amazing. It was 2,140% faster than the Array method. : 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. Note Ease of Use Using Segment Tree for this task was easier than using an Array. There was no need to create or methods to get the desired result. The Segment Tree had all the query methods built in. filter reduce The code snippet below contrasts the code required for Segment Tree and Array: Conclusion The Segment Tree is an 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. amazing 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.