Segment tree

A segment tree is a type of a data structure that is used to store information about array segments. This allows you to answer segment queries efficiently. 

You can perform the following two types of operations:

• range(i, j): This gives you the sum of the array elements starting at index i and ending at index j.
• update(i, val): This updates the value at index i to val in the original array and then updates the segment tree accordingly.

Construction of a segment tree

A segment tree can be represented in an array form. For this, let’s consider the following input array. The corresponding segment tree is as follows:

Input array

Segment tree

Note: The leaf nodes are the input array elements. Here, [i, j] represents the sum from input[i] to input[j].

Thus, the segment tree can be represented as an array in the following way:

For each element at index i of the segment array, its parent is located at index floor(i-1/2), its left child is located at index 2i+1, and its right child is located at index 2i+2.

To learn more about the segment tree, refer to this.

You can refer to this for some useful information on segment trees.

Task

Practice this question to help you solve the programming question in the practice test: Segment tree

Suffix tree

As the name suggests, a suffix tree is a type of a tree in which every suffix of a string S is represented. 

• A suffix tree T for an m-character string S is a rooted directed tree with exactly m leaves numbered from 1 to m. 
• Each internal node, other than the root, has at least two children.
• Each edge is labeled with a non-empty substring of S. 
• The key feature of the suffix tree is that for any leaf i, the concatenation of the edge-labels on the path from the root to leaf i exactly spells out the suffix of S that starts at position i. In other words, it spells out S[i..m].

The following example represents a suffix tree for the string ABC.

An interesting application of the suffix tree is discussed in this article.

Trie

Tries is a data structure that stores a collection of strings and allows you to search for a pattern in words easily. It provides fast pattern matching for string data values. 

Every node except the root stores a character value. 

All the children of a specific node are alphabetically ordered. 

Note: If any two strings have a common prefix then they have the same ancestors.

Trie with strings = {and, an, at, any}

Here is an interesting article on The trie data structure: A neglected gem. This article will allow you to understand why and how to use trie in your programming.

TAKE PRACTICE TEST 3

Are you ready to test your Data Structures Skills?

The Final Test