# Campus 101

6864 Registered Allowed team size: 1

This campaign is over.

hackathon
Online
starts on:
Dec 06, 2020, 06:24 PM
ends on:
Dec 06, 2020, 06:25 PM

## DS - Milestone 3

#### 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

 8 7 6 5 4 3 0 1 2 3 4 5

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:

 33 21 12 15 6 9 3 8 7 5 4

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.

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

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.