The motivation for binary indexed trees is similar to that of segment trees. However, note that segment trees are much more flexible than binary indexed trees, and usually its true that any problem that can be solved with BIT can be solved with segment trees but not the other way around.

Video tutorial: This is a superb tutorial, giving the motivation, walking through example, and going step-by-step through the pseudocode.

In this post I will introduce the concept of persistent data structures. We shall deal with a couple of problems: COT, MKTHNUM

Consider the following question:

Given a linked list, you need to support 2 operations.

1. Update the first x values.
2. Print the linked list after k’th update (k <= number of update operations made till now)

Simple solution is to create a new linked list after each update operation. print it when needed. Let us optimize it for memory.

We are only updating first x elements of the linked list. That means the new linked list will be almost same as previous linked list if x is small. We shall take advantage of this and avoid allocating memory for some elements. We can allocate memory for x elements, store new values in them, then point the next pointer of x’th node...

This is a very comprehensive 94-part course on competitive programming. It gets you from knowing basic programming to being a yellow-red rated coder on Codeforces / CodeChef / TopCoder / etc.

The primary objectives of this course are to learn about 30 different algorithms and data structures. The algorithm tutori...

Given an undirected weighted graph, a minimum spanning tree (MST) is a subset of the edges of the graph which form a tree and have the minimum total edge weight. For a MST to exist, the graph must be connected (that is, every pair of nodes must be reachable from each other).

Defining Greedy Algorithm

An algorithm is called greedy if it follows the problem-solving heuristic of making the locally optimal choice at each stage with the aim of finding a global optimum.

In most situations, a greedy strategy does not lead to the optimal solution. Hence, it is extremely important to reason about the correctness of the greedy strategy before using it to solve a problem.

Problem 1: Too much to do!

Let's say you have to maximise the number of tasks that you complete in a 10-hour duration. You are given an array T = [2, 4, 1, 6] where T_i denotes the time required to complete the i^th task.

The answer to this question would be 3 as you would choose to do tasks T₂, T₀ and T₁ — which take 1, 2 and 4 hours respect...