Problems Base course RU

Solves

range queries

Articles

DS Data structure Binary search tree Smaller to the left, larger to the right: search, order and the k-th element in the tree's height, from log n to n. O(h): from O(log n) to O(n) 2 problems DS Data structure AVL tree A search tree where the branch heights at a node differ by at most 1: height up to ~1.44·log₂ n. O(log n) for search, insertion and deletion 2 problems DS Data structure B-tree A tree with hundreds of keys in a page-sized node: a search among a billion keys reads five pages. O(log n) comparisons, O(log_B n) page reads 2 problems DS Data structure Fenwick tree Prefix sums with updates in O(log n) in a single array: blocks as long as the lowest one bit of the index. O(log n) per prefix sum and per update 2 problems GRA Algorithm Heavy paths Path queries on trees: heavy paths cut any path into O(log n) array stretches under a segment tree. O(log² n) per query 1 problem TEC Technique Coordinate compression Replace values up to a billion by their ranks in order, and build arrays and trees over the ranks. O(n log n) to compress 2 problems

Problems

A place in the catalogue How many people in a rectangle Words across chapters Flood watch

Often together

tree 4 classic 4 search tree 3 searching 3 databases 3 contests 3 interviews 2 array 2 geodata 2 selection 1 sliding window 1 operating systems 1