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 A of size N. A segment of the array is a contiguous part of an array in form A[i : j] such that 0 ≤ i ≤ j ≤ N-1.

A segment tree 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…


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 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 Equal Sum Partition Problem. I’d also highly recommend you to go through the Subset Sum Problem since it’s the parent problem for Equal Sum Partition Problem.

With that being said, let’s get started.

1. What is Equal Partition Sum Problem ?

Given a set of N non-negative integers, determine if the set can be partitioned into two subsets such that the 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 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 Subset Sum problem. I’d also recommend to go through the Knapsack Problem since it’s the parent problem for Subset Sum Problem.

With that being said, let’s begin!

1. What is Subset Sum Problem ?

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


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 Knapsack 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 W weight. We have a set of N items. Each item has an associated value v and an associated weight w. …


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 Dynamic Programming.

2. Recursion, Tabulation & Memoization

The key to understanding…


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 key in map is used to uniquely identify the element and the value 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 Enrolment Number is the key and Name is the corresponding value. The data type of the key…


Photo by Clément H on Unsplash

The Standard Template Library (STL) is a very useful set of template classes containing various containers. One among these containers is Lists. Today we’ll be having a look at Lists in STL. 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…


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…


Photo by Maxwell Nelson on Unsplash

The Standard Template Library (STL) 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

  1. Containers

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.

2. Algorithms

Algorithms, defined under the header <algorithm>, 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