CommonLounge is a community of learners who learn together. Get started with the featured resources above, ask questions and discuss related stuff with everyone.
Binary Indexed Trees (aka Fenwick Tree)
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.
Persistent segment trees: Explained with SPOJ problems
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.
Update the first x values.
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...
Motivation problem: We have a tree consisting of n(<=10^5) nodes. We will consider the tree nodes indexed from 1 to n. We will also consider the first node to be initially painted red, and the other nodes — to be painted blue. The distance between two tree nodes v and u is the number of edges in the shortest path between v and u. We need to learn how to quickly execute queries of two types:
paint a specified blue node in red;
calculate which red node is the closest to the given one and print the shortest distance to the closest red node.
Your task is to write a program which will execute the described queries.
Comments: It does seem like RMQ(Range Minimum/Maximum but on trees. Of course these can be solved using segment trees(Heavy Light Decomposition). But there is a technique which can be used to solved these kind of problems with the same time complexity but shorte...
Prerequisites: Matrix in algebra, Matrix multiplication
Introduction: Matrix Exponentiation (also known as matrix power, repeated squaring) is a technique used to solve linear recurrences. This technique is very useful in competitive programming when dealing with linear recurrences (appears along Dynamic Programming). This technique also solves a lot of problems in graph theory. Only solving recurrences is covered here, applications on graph theory will be discussed later.
Video tutorial: This video shows how you can use matrices to calculate the n-th fibonacci number (where n is very large ~10^18). You should be able to understand the technique after watching this video. Exercises will be added soon.
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).
Example of Minimum Spanning Tree. Total edge weight ...
This discussion is for expanding your array of maneuvers needed to code quickly and efficiently.
The first and most important thing that I'd like to discuss about is the C++ STL. Learning it would enable you to code up an assortment of algorithms and complicated data structures in a matter of seconds.
You can learn to use the C++ STL from the following amazing sites:
Studytonight : Contains syntax and examples for most of the STL containers and algorithms.
Sanfoundry : Shows how to implement what you've learnt in complete programs
Topcoder(Highly recommended) : This place teaches yo...