A comprehensive introduction to Segment Tree

Photo by Fotis Fotopoulos on Unsplash

1. What is a Segment Tree?

Let’s say we have an array of size . A of the array is a contiguous part of an array in form such that .

A is essentially a binary tree in whose nodes we store the information about the segments of a linear data structure such as an array. Do not worry about what kind of information as of now. We shall take a look at that in the later sections of this article.

  • The root node of the segment…


Dynamic Programming Problem #3 : Equal Sum Partition

Photo by Emile Perron on Unsplash

Before starting up with the Equal Sum Partition Problem, I would highly recommend you to read this introduction to . Here I have covered the basic method on how to approach a DP based problem. We will be using the same concepts to solve the . I’d also highly recommend you to go through the since it’s the parent problem for .

With that being said, let’s get started.

1. What is Equal Partition Sum Problem ?

Given a set of non-negative integers, determine if the set can be partitioned into two subsets such that the sum…


Dynamic Programming Problem #2 : Subset Sum

Photo by Safar Safarov on Unsplash

Before starting up with the Subset Sum Problem, I would highly recommend you to read this introduction to . Here I have covered the basic method on how to approach a DP based problem. We will be using the same concepts to solve the problem. I’d also recommend to go through the since it’s the parent problem for .

With that being said, let’s begin!

1. What is Subset Sum Problem ?

Given a set of non-negative integers and a target sum , determine if there exists a subset of the given set such that the sum of the…


Dynamic Programming Problem #1 : 0–1 Knapsack

Photo by Emile Perron on Unsplash

Before starting up with the Knapsack Problem, I would highly recommend you to read this introduction to Dynamic Programming. Here I have covered the basic method on how to approach a DP based problem. We will be using the same concepts to solve the problem.

With that being said let’s begin !

What is 0–1 Knapsack ?

The problem of 0–1 Knapsack goes something like this.

We are given an empty bag that can hold maximum of weight. We have a set of items. Each item has an associated value and an associated weight . …


Getting started with Dynamic Programming

Photo by Emile Perron on Unsplash

1. What is Dynamic Programming ?

In simple words, one can say that it is an optimization over plain recursion technique. This is achieved by reducing the number of recursive calls, either by storing the intermediate computed values or by deriving the final computation based on some kind of logical relation. This ultimately leads to reduced time complexities (from exponential to polynomial), thereby improving the overall performance of the solution.

Since it’s a programming paradigm thus it has nothing to do with being specific to a particular language or set of programming languages.

With that being said let’s dive into .

2. Recursion, Tabulation & Memoization

The key to understanding…


Getting started with STL in C++

Photo by Fotis Fotopoulos on Unsplash

What are Maps in STL ?

Maps are nothing but a type of associative container which stores elements in the form of key-value pairs. For those of you who are familiar with python, you can think of maps like a dictionary in python.

A in map is used to uniquely identify the element and the contains the corresponding stored data. Thus a key has to be unique and cannot repeat but the values can be same for two different keys.

Eg :

Enrolment Number : Name

Here is the key and is the corresponding value. The data type of the key…


Getting started with STL in C++

Photo by Clément H on Unsplash

The is a very useful set of template classes containing various containers. One among these containers is . Today we’ll be having a look at in . But before we proceed further I’d like to say that if this is your first time learning STL then I’d recommend you have a look at this article before beginning with this one.

With that being said let’s dive further into the topic by knowing what are lists in STL ?

A. Lists in STL

Lists are a type of sequence containers which provides us with constant insertion and deletion time anywhere…


Getting started with STL in C++

Photo by Safar Safarov on Unsplash

Iterators

Iterators are something which is used to point at the memory addresses of STL containers’ elements. Thus providing a means to access the data stored within the container and ability to modify them. They can be simply thought of as pointers.

Why Iterators ?

We need iterators in order to manipulate the containers. Containers on their own cannot be modified unless we make use of an iterator or a member function. The purpose is to isolate the user from the internal structure of the container thus helping with abstraction.

They provide a bridging or a connection between the algorithms and containers by allowing…


Getting started with STL in C++

Photo by Maxwell Nelson on Unsplash

The in C++ is nothing but a set of template classes which provides us with the widely used data structures such as lists, stacks, maps, etc. along with iterators, functions and algorithms in order to play around with the data elements.

A. Main Components of STL

Containers are nothing but holder objects which stores other objects i.e. it’s elements. A container does the memory management for its elements and provides us with member functions or iterators in order to interact with it’s data elements.

Algorithms, defined under the header , are nothing but a collection of several functions…

Tanishq Vyas

Student at PES University.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store