Creativity, Teaching & Engineering

The segment tree is the most commonly used data structure in competition programming. It is also extremely versatile and able to do many different operations that can hugely simplify many data structure problems. It is mainly used to do range update and range query.  Let’s start with the most basic version of the segment tree:…

Let’s assume we have the following problem: You are given a rooted tree where each node has a color. You want to count, for each subtree, the number of distinct colors that are within that subtree.  A naive solution is to DFS through each subtree, at each subtree you store a set containing all the…

A sparse table is a data structure that allows for range queries on a static array. It is most powerful when doing range minimum queries, as it can achieve O(1) time complexity with O(logN) processing.  WLOG we are doing range minimum queries on an array a.  The intuition of a sparse table is to store…

Tries, or Prefix Trees, are data structures used to store strings. In a Binary Search Tree, each node will store the entire key, whereas in a trie, each node’s position in the tree will determine the key that it represents.  Tries are essentially rooted trees where each node (except for the root), will store some…

All integers can be represented as bitmasks, strings of 0s or 1s. A bitmask of length N has 2^N states. It turns out that these bitmasks can be very useful in helping us solve a bunch of problems in time complexity of order O(2^N). In most cases, bitmasking helps us optimize from O(N!) time complexity…

Given two strings S1 and S2, we want to change S1 into S2 using the following operations: We want to find the minimal number of operations to convert S1 into S2.  We can solve this problem using dynamic programming.  DP[i][j] = minimum number of operations to change the first i characters of S1 into the…