Category: Competitive Programming

Update query (Range min query) For update query, we are given an index which needs to be updated. Let val be the value needed to be changed of a given node x. We start from the root of the segment tree and update all nodes (containing minimum value from given index) which have given index in their range. If a node doesn’t have a given index in its range, we don’t make any changes to that node.

A Trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. Trie is an efficient information reTrieval data structure and hence the name Trie. It is a special data structure used to store strings. It consists of nodes and edges like a tree.

Segment tree is a data structure that is used to solve a certain problem, called RMQ (Range Minimum Query).