Data Structure Sparse Table
Annotatsiya
This article discusses the sparse table data structure: description, capabilities, and scope of application. The results of comparison with such data structures as a segment tree and a sqrt decomposition for two problems are shown. Sparse Table is a data structure, that allows answering static range queries. It can answer most range queries in O(log n), but it efficiently answers range minimum queries (or equivalent range maximum queries) in O(1) time. It does preprocessing beforehand so that the queries can be answered efficiently. The origin of the data structure is related to the graph term lowest common ancestor. In graph theory and computer science, the lowest common ancestor (also called least common ancestor) of two nodes v and w in a tree or directed acyclic graph T is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor). We can solve the problem of finding the least common ancestor using a sparse table. The listing codes are presented in the C++ programming language.