A comprehensive introduction to 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.
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.
Given a set of N non-negative integers, determine if the set can be partitioned into two subsets such that the sum…
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!
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…
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 !
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. …
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.
The key to understanding…
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.
Enrolment Number : Name
Here Enrolment Number is the key and Name is the corresponding value. The data type of the key…
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 ?
Lists are a type of sequence containers which provides us with constant insertion and deletion time anywhere…
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.
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…
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.
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 <algorithm>, are nothing but a collection of several functions…
Student at PES University.