Introduction to Disjoint Set Data Strucutres

Hello Codeforces!

I recently read about Disjoint Sets from the book Introduction to Algorithms and wanted to share the learnings in a simplified manner.

So below article(and corresponding videos) is an attempt to create a good starting point for people who:

1. want to learn about DSU
2. practice some good DSU problems

Contents

1. Introduction through an illustrative problem (video version: https://youtu.be/JDycPHW4kIs?si=WEp5Ft2jBWp9KnO2)
2. Sample SPOJ Problem and Implementation (video version: https://youtu.be/O4w-aX5mSks?si=vr0XSbyUswcXx-Yv)
3. Upcoming Practice Problems
4. Some Applications and References

We will learn about disjoint set data structures and their operations union and find through a sample problem.

Illustrative Problem

Q: Given a undirected $$$Graph(V, E)$$$, answer Q queries of the form $$$(u, v)$$$ where answer to the query is True if there is a path from u to v, false otherwise.

So for above graph:

1. $$$query(D,A)$$$ = true
2. $$$query(D,C)$$$ = true
3. $$$query(D,F)$$$ = false

Some solutions to above problem

Solution1:

1. For each query $$$(u, v)$$$, perform a BFS/DFS.
2. Time Complexity will be $$$O(Q*(V + E))$$$
3. In worst case graph can have order of $$$V^2$$$ Edges.
4. So worst case complexity can be $$$O(Q*V^2)$$$

Solution2:

1. perform 1 BFS/DFS per node of the Graph
2. When BFS is done using node X, store all the nodes that can be visited from X.
3. Per Query time is $$$O(1)$$$ so overall $$$O(Q)$$$
4. Preprocessing time is $$$O(V * (V + E)) = O(V^3)$$$
5. Hence overall $$$O(Q + V^3)$$$

What is a Disjoint Set Data Structure?

1. It is a collection of disjoint dynamic sets. $$$D = {S1, S2, S3, …………, Sk}$$$
2. Each set has a Representative R and consists of some elements.
3. Assume total elements is N: $$$Size(S1) + Size(S2) + … + Size(Sk) = N$$$

A disjoint set structure supports:

1. $$$MAKE-SET(X):$$$ Creates a new Set with only element X and representative X.
2. $$$FIND(X):$$$ Returns the representative of the set to which X belongs.
3. $$$UNION(X, Y):$$$ Unites the sets containing the elements X and Y into a single new Set. The representative of this set is usually either the representative of Sx or representative of Sy

Diagramatic Example of a disjoint set with total 8 elements and 3 sets:

From above:

1. $$$Find(H) = G$$$
2. $$$Find(F) = F$$$
3. $$$Find(B) =Find(E) = A$$$

[Assume that A, G and F are representative elements their sets]

Using Disjoint Set DS for solving the problem

1. Run $$$MAKE-SET(u)$$$ for each of the V nodes in the graph.
2. Run $$$UNION(u,v)$$$ for each edge $$$(u,v)$$$ in the graph.
3. For each Query (u,v): a) If $$$FIND(u) == FIND(v)$$$ then answer = true b) Else answer = false

Running 1. and 2. on sample graph constructs the Disjoint set data structure shown in diagram.

Time complexity for DSU solution

Overall Complexity is sum of:

1. $$$O(V * MAKE-SET)$$$
2. $$$O(E * UNION) = O(V^2 * UNION)$$$
3. $$$O(Q * FIND)$$$

Disjoint Set — Linked List Implementation

1. Each set is represented as a link list.
2. The set has HEAD pointer to representative element and also a TAIL pointer.
3. Each element of the set has a back-pointer to the set.

Complexity Analysis for link list implementation

1. Make Set is O(1) -> only need to create a new set with 1 element
2. Find Set is O(1) -> thanks to back pointers
3. Union is length of the longer set -> no-thanks to back pointers(all of 2nd set element back-pointers need to be updated to 1st set)

Note: For a total of N elements in the collection there will be at most N-1 union operations as post that all elements will be in the same set.

Worst Case cost of Union is when:

1. All sets have size 1.
2. 1st union we unite two sets of size 1 and get a set of size 2 -> cost is 1 back pointer change.
3. 2nd time we unite a set of size 1 with a set of size 2 -> cost is 2 back pointer change.
4. ith time we unite a set of size 1 with a set of size i -> cost is i back pointer change.
5. Overall cost over n-1 union operations is $$$1 + 2 + 3 + .. + n-1 = O(N^2)$$$

Hence union is still $$$O(N)$$$ in the worst case.

Weighted Union Heuristic for link list Implementation

While performing $$$union(x,y)$$$:

1. Always take smaller set and attach it the larger set.
2. Need to maintain size of set for each set(which should be easy)

Complexity analysis: Union is now $$$O(logN)$$$, but why?

1. The cost of a union operation is the cost of changing back pointers of the elements in the smaller set.
2. Say we change the back pointer of an Element X belonging to $$$S_x$$$, the resulting set will have at least $$$2 * S_x$$$ elements.(since X belong to smaller set and hence it's backpointer was updated)
3. If back pointer of X is changed K times there need to be $$$>= (2^K) * S_x$$$ elements
4. K can be at most log(N) as we only have N elements.
5. hence for a given element we can change the back-pointer at most logN times and overall cost $$$<= NlogN$$$

Revisiting the sample problem

Worst Case complexity of Graph problem has now Improved :)

1. $$$O(V * MAKE-SET) = O(V)$$$
2. $$$O(E * UNION) = O(V^2 * UNION) = O(V^2 * logV) = O(V^2 * logV)$$$
3. $$$O(Q * FIND) = O(Q)$$$

So $$$O(V^2 * logV)$$$ instead of $$$O(V^3)$$$

Disjoint Set — Forest Implementation

1. Each set is represented as a tree.
2. Each element is a node of the tree and maintains a pointer to it's parent in the tree.
3. The representative element is the parent of itself.

$$$Find(X) = X \;if\,parent[X] = X \;else\,Find(X) = Find(parent[X])$$$

Forest Implementation — Time Complexities

We may still end up getting a chain :(

Worst case complexities:

1. UNION is $$$O(1) * O(FIND)$$$ in worst case(only need to change parent pointer of one representative to another, problem is finding the representative using FIND)
2. MAKE SET is $$$O(1)$$$ in worst case(only need to create a set with 1 element which is it's own parent)
3. FIND however is $$$O(N)$$$ in the worst case(we may end up getting a link list)

Time Complexities with Heuristics

Heuristic: Union by Rank

While performing union always take the Set(tree) with less height and attach it to the set with greater height.

1. Overall height after N-1 union will be order of LogN
2. Hence ensuring Find is no worse than LogN

Heuristic: Path Compression When performing find operation, change the parent pointer of each node to the actual representative of the node.

The time complexity when applying both heuristics together is:

1. Make Set is $$$O(1)$$$
2. Find Set is $$$O(\alpha(n))$$$
3. Union is amortised $$$O(\alpha(n))$$$

What is $$$\alpha(n)$$$?

1. Where alpha is the inverse of Ackerman function $$$A_k(1)$$$
2. $$$\alpha(n) <= 4$$$ for all $$$N <= 16^{512}$$$
3. $$$16^{512}\; »\; 10^{80}$$$
4. $$$10^80$$$ is the number of atoms in observable universe

Hence for all practical purposes $$$\alpha(n) = 4 = constant$$$.

Proof is harder and omitted from scope of this article, refer Introduction To Algorithms by Thomas H. Cormen

Revisiting the sample problem

1. Make Set is $$$O(1)$$$
2. Find Set is $$$O(1)$$$
3. Union is $$$amortised O(\alpha(n))$$$

Worst Case complexity of Graph problem has now Improved :)

1. $$$O(V * MAKE-SET) = O(V)$$$
2. $$$O(E * UNION) = O(V^2 * UNION) = O(V^2 * logV) = O(V^2 * \alpha(V))$$$
3. $$$O(Q * FIND) = O(Q)$$$

Hence time complexity is now $$$O(V^2 + Q)$$$ for all practical purposes.

SPOJ Problem — FRNDCIRC + Generic Implementation

• Problem Link: https://www.spoj.com/problems/FRNDCIRC/
• Solution link: https://youtu.be/O4w-aX5mSks?si=UQJwpjayddjVK5uw
• Code implementation: https://ideone.com/Bdh2It

Upcoming Practice Problems

Currently I have planned the problem https://mirror.codeforces.com/problemset/problem/150/B and will be soon adding both a written and video editorial for the same.

Few other practice problems include: https://mirror.codeforces.com/blog/entry/55219?#comment-390897 (DSU tag). I will be using some of these to create more editorials.

If you have more suggestions please add in comments.

Applications and References

Some direct applications:

1. Finding cycles in a graph
2. Kruskals minimum spanning tree algorithm

Some references:

1. https://www.youtube.com/@AlgosWithKartik
2. Introduction to Algorithms Book
3. CP algorithms: https://cp-algorithms.com/data_structures/disjoint_set_union.html

Hello Codeforces!

It's been a while since I contributed something useful to the CF community. So here I am trying my best to make some high quality lectures on range query data structures!

For trying out some range query problems: head to cses range query section
For solutions: my previously written cf blog

Video Series for range query DS

Range Query Problems and Data Structures

Video link: https://youtu.be/8wJzUFZOqK4
Welcome to the series on Range Query data structures and problems!! In this video we will discuss:
1. What are range query problems?
2. Types of Range query problems.
3. Online queries vs offline queries.
4. point updates and range updates.
5. Common Range Query Data Structures for efficiently solving these problems.

Prefix Arrays

Video link: https://youtu.be/-_Jj4U5V4N0
We will talk about:
1. What are prefix arrays?
2. How to build them.
3. How to use them to answer queries.
4. Why can't we use them for range min or max queries?
5. Building a library for solving range query problems using prefix arrays.

Sparse Table | Range Minimum Query in O(1)

Video link: https://youtu.be/iaRvydtqLV4
Introduction to Sparse Table.
Solve Range Min Queries in O(1) time.

1. what is sparse table?
   
2. how to build a sparse table?
   
3. how to use it to solve queries?
   
4. Cpp code.
   

Square Root Decomposition

Video link: https://youtu.be/ZakhE_eaonY

Gentle introduction to Square Root Decomposition.
implementation of the idea discussed in the video: cpp code​

To solve the problem of answering range queries on an Array A[1..N].
Queries are of two types:
1. find function F applied on the range [L,R]. F can be sum, min, max or wide range of other functions.
2. point update. set A[i] = new_value V.

Algorithm:

 1. Break Array A into X smaller chunks each with Y elements.
 2. Find F applied over each chunk individually.

Why exactly root N chunks each with root N elements?

Upcoming topics

1. Mo's algorithm over arrays and trees.
   
2. Segment trees with/without lazy propagation.
   
3. Fenwick tree
   
4. Persistent data structures.
   
5. CF/CC/SPOJ Problem solving using above data structures
   

Hope people will find this useful.
Will keep updating this blog with more content.

Happy Coding :)

Hello codeforces

I liked solving today's contest(on pen and paper :p) and I am sharing the solutions for problems A to D. hope this might help some of you :)

quick editorial for problems A to D

problem A

given n and b. find a such that a + b is maximum possible.

b = B[0] B[1] .... B[n-1]
a = A[0] A[1] .... A[n-1]

sum[i] = A[i] + B[i]

observations:
since we want sum to be as large as possible we want:
1. sum[0] to be as large as possible(hopefully 2 otherwise 1)
2. an integer with more digits is large, so we would like to retain all digits.

to retain all digits make sure sum[i] != sum[i-1]

go for a brute force to determine a.
find A[0] with no constraint. then find A[i] such that A[i] is not equal to A[i-1] and A[i] is as large as possible(2 > 1 > 0).

problem B

we need to find num such that num has atleast 4 divisors and the divisors have atleast a space of d among them.

any number > 1 has atleast two divisors: 1 and the num itself.
our 3rd divisor(d3) should be atleast 1 + d
and our 4th divisor(d4) should be atleast 3rd_divisor + d

if 3rd and 4th divisors are prime then our number will be equal to d3*d4.
any number can be represented as a product of primes.
num = d3*d4 where both d3 and d4 are prime is the best possible choice.

why? please provide good mathematical proof else I will provide a proof after writing other solutions.

so simply select d3 as the smallest prime number greater than 1 + d and select d4 as the smallest prime number greater than d3 + d.

final answer = d3*d4

problem C

sort the array.

observations:
1. always need to select the largest element of the array. why?
2. initially I may select any element a[i] (1 <= i < 2*n) along with a[2*n] and remove them.
3. thus x = a[i] + a[2n]

let us I say I selected the integers a[2n] and a[i] in the first move to delete. so ** x** is fixed.
for the remaining array also the observation 1 holds true.

make a table of the elements you have in the array.
map<int,int> element. where element[i] = j means that i appears j times in your remaining array.

to perform an operation you will select the largest element of the array i.e. L1, now you need an element from the array equal to L2 such that L1 + L2 = x

if element[L2] != 0 then you are good. and you should do:

 element[L1]-- delete L1 
 element[L2]-- delete L2 
 x = max(element[L1], element[L2]) new value of x 

Simply try this for all possible i. that is for all possible initial element selected along with a[2n]

problem D(hint)

most crucial observation:

a[1] has only 1 neighbor and same for a[n]. try solving with this in mind.
so a[1] has to be reduced to 0 with complete help from a[2] no matter what(unless we use super power)

let us not use the super power.

after reducing a[1] with help from a[2], remaining portion of a[2] is now in a similar position: only 1 neighbor i.e. a[3]

try using superpower to swap a[i] and a[i+1] then answer is yes if:

you should be able to solve the array[1:i-2] and array[i+3:n] with only help from a[i-1] and a[i+2](precompute these values for all i). after this check if you can solve for array {some portion of a[i-1], a[i+1], a[i], some portion of a[i+2]}

i will shortly add a more detailed editorial for problem D

in more detail

first check if subarray A[1:i] can be solved without the use of superpower.(1 <= i < N)

cool, how to check?
A[1:1] can be solved if and only if A[1] is less than or equal to A[2] otherwise A[1:1] cannot be solved.
A[1:2] can be solved if A[1:1] can be solved and (A[2] — A[1]) <= A[3]
If I choose to solve A[1:1] without superpower it leaves an effect on A[2]. it reduces the value of A[2] to A[2] — A[1].
let me call this reduced_left[2] or reduced_left[i].

A[1:i] can be solved if A[1:i-1] can be solved and reduced[i-1] <= A[i]

reduced_left[i + 1]: in order to solve A[1:i] what was the value of A[i+1] reduced to.

second check if subarray A[i:N] can be solved without the use of superpower.(2 <= i <= N)

A[N:N] can be solved if and only if A[N] is less than or equal to A[N-1] otherwise A[N:N] cannot be solved.
on similar lines you will get a definition of reduced_left[i].

now answer is yes if A[1:N] is solvable assuming A[N+1] = A[0] = 0 (without use of superpower)

answer is also yes if I can swap A[i] and A[i+1] such that:
i. A[1:i-2] can be solved without superpower.
ii. A[i+3:N] can be solved without superpower.
iii. the array { reduced_left[i-1], A[i+1], A[i], reduced_right[i+2] } can be solved without superpower

try this for all i from 1 to N-1.

5. otherwise answer is no.

hope this helped.

Just wanted to share some useful content on binary search with the people here at codeforces!

Binary search is best visualized as searching for a value X at which F(X) = Y where "F" is some function.

This notion of binary search can help efficiently evaluate:
->Local minima and Local maxima of a function.

you can evaluate things like:

1. highest point for a projectile using binary search

2. nth root of a number.

3. Cost minimization techniques like gradient descent and binary search play a crucial role in machine learning.

Here is a short playlist which outlines the essence of binary search in detail with lots of real-life examples and 6 interesting problems that can be solved with binary search.

link: https://www.youtube.com/playlist?list=PLb3g_Z8nEv1jH8cmcMrx_6MuM_KC_LIan

Do share some fun real-life applications of binary search in comments!

Hello Codeforces!

This blog is here to compile the resources that I have created over the past 6 months. I had started with the goal of creating a useful course on algorithms and problem solving, overall I wanted to provide high quality material which is free.

So I started with the most interesting topic(for me) dynamic programming and developed an extensive course on the same.

I feel the course is extremely useful for beginners as well as intermediates to get better at dp, learn some useful techniques and improve their problem solving skills. From the limited reviews that I have received on the content till now I can say that people have found my the content useful and explanations better than many paid courses which people usually opt-for.

I wanted to share the overview of the course here so it can reach more people.

Overview

Basics of DP:

I start with the very basics of DP so that someone with even 0 knowledge of the subject can follow. I start-off with easy problems from CSES and then slowly take the viewers from there to harder problems like CF div2E or rated-2400 problems on CF. I have created over 20+ illustrative problems for the viewer each with detailed explanation and code.

You can check the playlist here: DP from scratch

DP on Trees:

I have created another playlist/course for dp on trees. Here again the viewer will start with some very simple dp on tree problems and then we slowly ramp up the difficulties to problems from codeforces(rating-2000+). I describe techniques like rerouting, binary lifting and many more in detail. I discuss around 10 problems in detail with code so the viewer can have a good grasp over the concept of dp on trees.

Check the playlist here: DP on Trees

Digit DP:

I start by explaining the concept and application of digit dp followed by some illustrative problems from SPOJ, codechef and google kick start.

Link to the playlist: DIGIT DP

DP with Bitmasking:

We will start with some classical problems like job assignment and travelling salesman and see how dp can be applied to these problems through the use of bitmasks. I will also describe what bitmasks are in a seperate video. Later we will solve some harder problems which involve the concept of bitmasking and DP from OJ's like codechef and codeforces.

check the playlist here: DP with Bitmasking

More Content

You can also checkout some of the other playlists on my channel like the one's on Binary Search, Coding interview problems, Codeforces problems and many more!

I also plan a series on graphs, hopefully sometime soon!

Make sure to checkout my channel and if you find it useful show support by subscribing to it and letting me know you like the content and effort through some nice comments :)
Hope that this course on dynamic programming will help many!

Hello Codeforces!

This series of videos are focused on explaining dynamic programming by illustrating the application of digit DP through the use of selected problems from platforms like Codeforces, Codechef, SPOJ, CSES and Atcoder.

After going through this series, you should find yourself confident in solving problems which require the use of digit dp and also implementing them in a reasonable amount of time.

I will also live code and submit the solutions to the problem on the coding platform from where the problem comes.

Some Basic elements of Dynamic Programming

Some general ideas and my thoughts about DP to help you get started:

Part 1: https://youtu.be/24hk2qW_BCU
1. What is Divide and Conquer?
2. What is Dynamic Programming?
3. Types of DP problems.

Part 2: https://youtu.be/yfgKw6BUZUk
1. What is a DP-state?
2. Characterizing a DP-state.
3. What is a recurrence?
4. Top Down v/s Bottom Up.

Part 3: https://youtu.be/X-3HklSPx6k
1. Directed Acyclic Graph(DAG) Representation of DP solution
2. Visualizing Top-Down and Bottom-Up.
3. Evaluation order for bottom-up codes.
4. Analyzing the space and time complexity for a DP solution(derivation).

You may also want to checkout these video tutorials:
- Beginner Friendly Series on Dynamic Programming
- Dynamic Programming on Trees
- Introduction to DP with Bitmasking

Introduction to Digit DP

I discuss the following concepts in this video:

1. What exactly is Digit DP?
   
2. What are the types of problems I can solve with Digit DP?
   
3. Discussing a sample problem and it's brute force solution.
   
4. Building up an intuition towards a DP based solution.
   
5. Further discussing another concept required for solving Digit DP problems.
   
6. Coding the solution which we came up with.

video link: https://youtu.be/heUFId6Qd1A

Google Kick Start Round H 2020: Boring Numbers

I'll discuss a problem named boring numbers that comes from a Google kick start round.
Problem link: google kick start problem
Solution: https://youtu.be/2yAEj-0A8bk

SPOJ: Digit Sum

Problem link: https://www.codechef.com/problems/ENCODING
Solution: https://www.youtube.com/watch?v=H6OCV7qcZoQ

Codechef long: Encoding

Problem link: https://www.spoj.com/problems/PR003004/
Solution: https://youtu.be/B7ZWUBfaIq0

CSES: Counting Numbers

Problem link: https://cses.fi/problemset/task/2220
Solution: https://youtu.be/lD_irvBkeOk

Practice Problems:
1. https://www.spoj.com/problems/CPCRC1C/
2. https://www.spoj.com/problems/NUMTSN/
3. https://www.spoj.com/problems/PR003004/
4. https://mirror.codeforces.com/contest/628/problem/D
5. https://mirror.codeforces.com/gym/100886/problem/G

Will be adding more videos soon!
Hope people find this helpful :)

UPD: added spoj digit sum and codechef enocding. This is the last video for this series(at least for now) unless there are many people who want more.
UPD: added solution to standard digit dp problem from CSES, namely counting numbers.

So I had proposed a problem few months back but didn't get the time to prepare an entire contest. Wanted to share the problem and it's editorial which I wrote while proposing.

Came across something similar while reading and implementing a research paper.

n = 3, m = 2.
SIM :
10 6 -4
6 10 -2
-4 -2 10

all possible 2 sized subsets are {1,2}, {1,3}, {2, 3}.
score for d1 = max{(10+6), (10-4), (6-4)} = 16
score for d2 = max{(6+10), (6-2), (10-2)} = 16
score for d3 = max{(-4-2), (-4+10), (-2+10)} = 8

possible answers 1 and 2, choose the minimum.
therefore output 1.

Brute force : Overall complexity : n * binomial_coeff(n,m)

DP : dp[i][j][k] = max(dp[i][j-1][k], SIM[i][j] + dp[i][j-1][k-1]), score for the ith item, taking a k sized subset of the 1st j items.
Si = dp[i][n][m].
Overall complexity : n*n*m

Greedy1 : for every i,
put all values SIM[i][j] for all j from 1 to n in a vector. sort this vector, take sum of last m items. This is Si.
Overall complexity : n*n*log(n)

Greedy2 : Use heap instead of sorting.
Overall complexity : n*n*log(m)

Problem Origin: equation number 2 in the paper "Exploring Nearest Neighbor Approaches for Image Captioning"

Hope you enjoy solving the problem :)
also let me know what difficulty you think should be assigned to this problem.

Hello Codeforces!

This series of videos are focused on explaining dynamic programming by illustrating the application of DP with bitmasking through the use of selected problems from platforms like Codeforces, Codechef, SPOJ, CSES and Atcoder.

After going through this series, you should find yourself confident in solving problems which require the use of dp and bitmasks and also implementing them in a reasonable amount of time.

I will also live code and submit the solutions to the problem on the coding platform from where the problem comes.

Some Basic elements of Dynamic Programming

Some general ideas and my thoughts about DP to help you get started:

Part 1: https://youtu.be/24hk2qW_BCU
1. What is Divide and Conquer?
2. What is Dynamic Programming?
3. Types of DP problems.

Part 2: https://youtu.be/yfgKw6BUZUk
1. What is a DP-state?
2. Characterizing a DP-state.
3. What is a recurrence?
4. Top Down v/s Bottom Up.

Part 3: https://youtu.be/X-3HklSPx6k
1. Directed Acyclic Graph(DAG) Representation of DP solution
2. Visualizing Top-Down and Bottom-Up.
3. Evaluation order for bottom-up codes.
4. Analyzing the space and time complexity for a DP solution(derivation).

You may also want to checkout these video tutorials:
- Beginner Friendly Series on Dynamic Programming
- Dynamic Programming on Trees

About the series

Short video where I talk about the playlist: https://youtu.be/6sEFap7hIl4

What is Bitmasking

I talk about what is bitmasking before we actually start solving problems that use dp with bitmasking.
https://youtu.be/7FmL-WpTTJ4

Illustration: Solving the Job Assignment Problem

Using a simple problem, I will illustrate how to solve and implement problems which use dp+bitmask concepts.
Problem link: statement
Solution: https://youtu.be/685x-rzOIlY

Illustration: Travelling Salesman Problem

Another great problem to illustrate bitmask dp.
I will discuss the following:
1. What is the TSP?
2. Brute force solution.
3. Intuition towards an efficient solution.
4. Define a DP state, write a recurrence.
5. How do I implement this? ANS: bitmasking!
6. Analyzing time and space complexities.

Link: https://youtu.be/QukpHtZMAtM

Codeforces Problem: Div2E

I'll discuss a problem named Fish that comes from a Codeforces Divison 2 round.
Problem link: https://mirror.codeforces.com/contest/16/problem/E
Solution: https://youtu.be/d7kvyp6dfz8

Codechef long Challenge: Medium

The problem comes from Codechef long challenge and is rated MEDIUM by codechef.
Problem link: https://www.codechef.com/problems/TSHIRTS
Solution: https://youtu.be/Smem2tVQQXU

CSES: Counting Tilings

The problem comes from CSES problemset and was introduced to the problemset in 2021.
Problem link: https://cses.fi/problemset/task/2181
Solution: https://youtu.be/lPLhmuWMRag

Practice Problems:
1. https://atcoder.jp/contests/dp/tasks/dp_o
2. https://atcoder.jp/contests/dp/tasks/dp_u
3. https://www.codechef.com/JAN13/problems/LEALCO
4. https://www.spoj.com/problems/HIST2/
5. https://mirror.codeforces.com/problemset/problem/895/C

If people find this helpful then I will try and add more problems to this list :)

This series of videos are focused on explaining dynamic programming by illustrating the application of DP through the use of selected problems from platforms like Codeforces, Codechef, SPOJ, CSES and Atcoder.

After going through this series, you should find yourself confident in approaching dynamic programming problems and also implementing them in a reasonable amount of time.

I will also live code and submit the solutions to the problem on the coding platform from where the problem comes.

Some Basic elements of Dynamic Programming

Some general ideas and my thoughts about DP to help you get started:

Part 1: https://youtu.be/24hk2qW_BCU
1. What is Divide and Conquer?
2. What is Dynamic Programming?
3. Types of DP problems.

Part 2: https://youtu.be/yfgKw6BUZUk
1. What is a DP-state?
2. Characterizing a DP-state.
3. What is a recurrence?
4. Top Down v/s Bottom Up.

Part 3: https://youtu.be/X-3HklSPx6k
1. Directed Acyclic Graph(DAG) Representation of DP solution
2. Visualizing Top-Down and Bottom-Up.
3. Evaluation order for bottom-up codes.
4. Analyzing the space and time complexity for a DP solution(derivation).

Problem 1: Dice Combinations

Source: CSES
Problem link: https://cses.fi/problemset/task/1633
Explanation: https://youtu.be/5gd5jptXWAM

Problem 2: Coin Combinations I

Source: CSES
Problem link: https://cses.fi/problemset/task/1635
Explanation: https://youtu.be/5BdAl6gfusg

Problem 3: Coin Combinations II

Source: CSES
Problem link: https://cses.fi/problemset/task/1636
Explanation: https://youtu.be/-pXjopzMVrE

Problem 4: Removing Digits

Source: CSES
Problem link: https://cses.fi/problemset/task/1637
Explanation: https://youtu.be/32qvB7OP4V8

Problem 5: Grid Paths

Source: CSES
Problem link: https://cses.fi/problemset/task/1638
Explanation: https://youtu.be/V64F4wlodUM

Problem 6: Book Shop

Source: CSES
Problem link: https://cses.fi/problemset/task/1633
Explanation: https://youtu.be/qpNy2nuSuaI

Problem 7: Array Description

Source: CSES
Problem link: https://cses.fi/problemset/task/1158
Explanation: https://youtu.be/d1H5JylYG4I

Problem 8: Edit Distance

Source: CSES
Problem link: https://cses.fi/problemset/task/1639
Explanation: https://youtu.be/Ev80c1oIRFg

Problem 9: Rectangle Cutting

Source: CSES
Problem link: https://cses.fi/problemset/task/1744
Explanation: https://youtu.be/LdynQjWsO5Q

Problem 10: Two Sets II

Source: CSES
Problem link: https://cses.fi/problemset/task/1093
Explanation: https://youtu.be/TOsD3BkIKoQ

Problem 11: Beautiful Array

Source: Codeforces
Problem link: https://mirror.codeforces.com/problemset/problem/1155/D
Explanation: https://youtu.be/IgBLv32QFoQ

Problem 12: Number of Valid Arrays

Source: Coding Interview
Problem link: Problem Statement
Explanation: https://youtu.be/QGJXQAaDs3I

Problem 13: Longest Increasing Subsequence O(NlogN)

Source: CSES
Problem link: https://mirror.codeforces.com/problemset/problem/1155/D
Proof and optimization to NlogN: https://youtu.be/66w10xKzbRM
Implementation of the algorithm: https://youtu.be/wqLwv7E1GF0

Problem 14: Projects

Source: CSES
Problem link: https://cses.fi/problemset/task/1140
Solution Approach: https://youtu.be/MJn3ogwsUbo
Implementation of the algorithm: https://youtu.be/ISuIwMnSyXc

Problem 15: Beauty of Tree

Source: Kick Start
Problem link: Long link
Explanation: https://youtu.be/ueLRceYVcdE

Problem 16: Catch Some

Source: Kick Start
Problem link: Long link
Explanation: https://youtu.be/ljLIrNKLANE

Problem 17: Vasya and Binary Strings

Source: Codeforces (rated:2400)
Problem link: https://mirror.codeforces.com/problemset/problem/1107/E
Explanation: https://youtu.be/NINZAQFW_AE

Problem 18: Counting Towers

Source: CSES 2021 problem
Problem link: https://cses.fi/problemset/task/2413
Explanation: https://youtu.be/pMEYMYTX-r0

I am quite confident that many beginners/intermediates will definitely enjoy watching this series on dynamic programming and it will definitely help in getting better at dynamic programming and problem solving in general. I have tried to teach in a way such that not many prior prerequisites are required to understand the explanations even to the harder problems.

If people find this helpful then I will make sure that this list of problems will keep growing, cheers!

Link for introduction to DP on Trees: https://mirror.codeforces.com/blog/entry/79857

UPD: Added 2 more problems from CSES: Projects and Removing digits.
UPD: Added 3 parts on basic elements of DP to get you started.

UPD: I have also started a series on DP with bitmasking(starting from the very basics) and in the future will make a separate blog for both Digit DP series and DP with bitmasking series, till then interested people can check: Dynamic Programming with bitmasking
UPD: added solution to problem Vasya and Binary Strings
UPD: added solution to problem Counting towers from CSES

Hello Codeforces!!

In this blog, I want to present to you a beginner-friendly video lecture series on dynamic programming on trees/an editorial for the CSES tree algorithms section.

CSES is a brilliant problemset for people wanting to get started at competitive programming and get good at it.

My aim till now has been to make the explanations intuitive, crisp and clear. I feel even a beginner will be able to benefit from these video lectures.

So let's get started.
Link to the problems

Subordinates

Explanation : https://youtu.be/fGznXJ-LTbI
AC code : https://github.com/kartik8800/CSES/blob/master/Subordinates

Tree Matching

Somehow I feel some other nice approaches are also possible, please do share.
Explanation : https://youtu.be/RuNAYVTn9qM
AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Matching

Tree Diameter

Explanation : https://youtu.be/qNObsKl0GGY
AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Diameter

Tree Distances I

This problem uses the rerooting technique, we evaluate the answer for every node assuming it to be the root of the tree. If we do this naively this will be O(N^2) time but if we do this using something known as the reroorting technique and propogate partial answers of parent node with respect to the child nodes we can optimize our solution to O(N) overall time complexity.
I feel Tree Distances II is easier compared to Tree Distances I and would recommend to try it first.

Explanation : https://youtu.be/N7e4CTfimkU
AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Distances%201

Tree Distances II

This problem also uses the rerooting technique.
Explanation : https://youtu.be/nGhE4Ekmzbc
AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Distances%202

Distance in Tree

This problem also uses the rerooting technique.
Problem link: https://mirror.codeforces.com/contest/161/problem/D
Explanation : https://youtu.be/SOhZqL6HPjQ

Company Queries I

This problem uses a technique(the technique itself uses DP) known as Binary lifting. I will be adding a detailed lecture on binary lifting with code.

Explanation : https://youtu.be/FAfSArGC8KY

Company Queries II

This problems requires us to know a technique to calculate LCA of two nodes in a tree in O(logN) time. Evaluation of LCA in O(logN) can be done using binary lifting. I will add a more detailed video soon.

LCA using binary Search: https://youtu.be/qPxS_rY0OJw
LCA slightly different from standard algorithm: https://youtu.be/s9zZOVsF_eo

Distance Queries

Problem Statement : what is the distance between nodes a and b?
Short explanation : Let LCA(a,b) be node x, what is distance between a and x?
Preprocess the levels of all the nodes in the tree.

lvl[i] : level of node i in the tree.
Ans to query distance(a,b) = (lvl[a] — lvl[x]) + (lvl[b] — lvl[x]) where x is the LCA(a,x).

Again finding LCA of two nodes can be done in O(logN) time and levels of all nodes can be found in O(N) time preprocessing.
Explanation: https://youtu.be/i9ctLWyVSsA

Appleman and tree

problem statement: https://mirror.codeforces.com/problemset/problem/461/B
solution video: https://youtu.be/gj0zp--fBL8

Binary Tree Cameras Leetcode

problem statement: https://leetcode.com/problems/binary-tree-cameras/
solution video: https://www.youtube.com/watch?v=VBxiavZYfoA

I am also planning to add video lecture series on more topics which might be helpful to beginners as well intermediates. I will be open to feedback and suggestions.

I hope people find this helpful :)

UPD: added detailed explanation for binary lifting and video solution to Company Queries I.
UPD: added detailed explanation for LCA techniques.
UPD: added solution to distance queries(CSES) and Distance in Tree(CF, VKCup,Problem D).
UPD: added solution to appleman and tree from codeforces.
UPD: added solution to binary tree cameras from leetcode.

Hello Codeforces!!

Recently I was fascinated about two of the most amazing things in the world : money and ofcourse algorihtms xD. I saw some interesting games played at casinos and I thought about one of them for quite a while : The Roulette.

The Roulette

Consider a spinning wheel with numbers from 1 to 12 marked on it. Each number has an equal probability of showing after the wheel has stopped spinning. The player(will avoid the word gambler) has the following power : he may bet some coins on either odd/even. Let's say the player bets x coins on even. If the roulette after spinning shows an even number than the player gets 2x coins otherwise he loses x coins. Similarly if the player bets x coins on odd then he will win 2x coins if roulette shows an odd number after spinning.

Possibility of an Algorithm for winning?

So is it possible for us to design a sure-shot algorithm that can guarantee the player to win some profit?

Then why are we even here?
So it might not be possible to guarantee a profit but maybe we can come up with strategies/algorithms that make a certain amount of profit with a certain confidence/probability.

Motivation : The Martingale Algorithm

So the martingale algorithm in my opinion is simple and brilliant with a great deal of drawbacks.
Suppose that we wish to make a profit of x coins.
Here is the algortihm:

 Let X be an integer.
 1. Bet X coins on odd.
 2. Let the roulette spin.
 3. If outcome is odd, go to step 5.
 4. X := 2 * X and go to step 1.
 5. END.
 

Wonderful, isn't it? Sorry to say that it has a great deal of drawback because to be fair it has only 1 drawback.

Also another drawback which for now we will overlook : usually casinos have an upper limit on the bet you can place. In the very unlikely event of lots of consecutive loses there will be a disaster.

"I have enough coins and the amount of profit I want to make is considerably smaller, nearly 1% of the coins I have. What is the chance I stand to win this profit using martingale algorithm?"

Cooool, so now probably I should give some modified or new strategy for higher winning chances? No, instead I am here with a challenge.

The Challenge

You are given 10K coins, you need to come up with an algorithm/strategy which stands a good chance of winning/making profits.

There will be exactly 5K roulette spins, giving you the opportunity to make bets.

I am super interested in people coming up with some algorithms that maximize the chance of winning.

So here is the challenge, design a strategy and implement it to check what profit do you make. Here I am providing a template code in which the user simply needs to implement the make_bet() function. Basically you will be building a betting bot to play roulette for you and earn as much as possible.

What about the bot getting lucky? How will scoring be done?

A few rules :
Try to keep your bot deterministic/don't use rand() in your make_bet function.
Do not try to utilize the pseudo-randomness of rand(), if that is a possibility.

I know we all would love to maximize the score of the bot.
Here is the template code : Betting Bot challenge
Hope people find this fun and interesting.

P.S. Do not gamble :)

UPD: some video editorials on range query data structures: youtubePlaylist

Hello Codeforces, In this blog I will try to write a well detailed editorial for the CSES Range Queries section. The motivation for this editorial comes from https://mirror.codeforces.com/blog/entry/70018.

Quoting icecuber "I think CSES is a nice collection of important CP problems, and would like it to have editorials. Without editorials users will get stuck on problems, and give up without learning the solution. I think this slows down learning significantly compared to solving problems with editorials. Therefore, I encourage others who want to contribute, to write editorials for other sections of CSES."

So here I am writing an editorial for the range queries section.

If you find any error or maybe have a better solution to some problem please do share.

Range Sum Queries I

Given array is A[1..N], for each query of form (L,R) we need to output A[L] + A[L+1] + ... + A[R].
Define an array Prefix such that Prefix[i] = A[1] + A[2] + .. + A[i].
Prefix[R] = A[1] + A[2] + ... + A[R] and Prefix[L-1] = A[1] + A[2] + ... + A[L-1].
Consider Prefix[R] — Prefix[L-1] = (A[1] + A[2] + ... + A[R]) — (A[1] + A[2] + ... + A[L-1]) = (A[L] + A[L+1] + ... + A[R]).

So for every query simply output Prefix[R] — Prefix[L-1].

prefix[0] = 0
for i = 1 to N
     prefix[i] = ar[i] + prefix[i-1]

Time complexity : O(N) to build prefix array and O(1) per query.

Range Minimum Queries I

Two possible ways are as follows :
1. Build a Range minimum query segment tree in O(N) time and answer each query in O(logN).
2. Build a sparse table in O(NlogN) time and answer each query in O(1).

int small(int x,int y){return min(x,y);}
SegmentTree < int > rangeMinQueries(dataVector,INT_MAX,small);
For answering a query : rangeMinQueries.query(l,r)

Refer https://mirror.codeforces.com/blog/entry/71101 for my segment tree template.

Approach 2 : https://cp-algorithms.com/data_structures/sparse-table.html

Range Sum Queries II

So this one is a direct use of segment tree with point updates and I shall use my segtree template to answer this problem.

vector dataVector(n); 
ll sum(ll x,ll y){return x+y;}
SegmentTree < ll > rangeSumQueries(dataVector,0,sum);
For query of type 1 : rangeSumQueries.update(idx,newVal);
For query of type 2 : rangeSumQueries.query(a,b);

Both of these queries can be performed in logN time.
Overall time complexity is O(N) for building segtree and QlogN for Q queries.

Range Minimum Queries II

Again a straightforward segment tree problem and I will use a similar code as I used for the previous problem. This is the same as RMQ1 except that here we also have point updates. Segment tree solution for RMQ1 and RMQ2 will be identical.

vector dataVector(n); 
int small(int x,int y){return min(x,y);}
SegmentTree < int > rangeMinQueries(dataVector,INT_MAX,small);
For query of type 1 : rangeMinQueries.update(idx,newVal);
For query of type 2 : rangeMinQueries.query(a,b);

Both of these queries can be performed in logN time.
Overall time complexity is O(N) for building segtree and QlogN for Q queries.

Range Xor Queries

For this problem we can maintain a segment tree where each node of the tree will store the xor-sum of the range of elements for which it is responsible.
So root of the tree stores : A[1]^A[2]^....^A[N].

To calculate the answer for a particular interior node of the tree we do :
NODE_VAL = LEFT_CHILD_VAL ^ RIGHT_CHILD_VAL
For leaf nodes :
NODE_VAL = A[x], where [x,x] is the range this leaf node is responsible for and if x > N then NODE_VAL = 0 as 0 is the identity for xor_sum.

Again with these observations we can use the same segtree template as follows :

vector< int > dataVector(n); 
int xor_sum(int x,int y) { return x^y; }
SegmentTree< int > xorSumQueries(dataVector, 0, xor_sum);
For answering the query : xorSumQueries.query(l,r)

AC code : https://ideone.com/mPhqas

Range Update Queries

Nice question which can be directly solved with a segment tree with lazy propagation but that is an overkill plus my segtree library does not support lazy propagation as of now.

Let's define a few terms:
SUM[i] = overall update done on the ith element till now
Initially SUM[i] = 0 for all i as no updates have yet been performed, now we would like to track the updates happening so that our answer to a query 2 k can easily be v[k] + SUM[k] where v is the initial array.

How to efficiently maintain the SUM array? Let us build a range sum query segment tree on some array X which has all elements initialized to 0.

DEFINE : RSQ[i] = X[1] + X[2] + .. + X[i] = rangeSumQuery(1,i)

Now say we have a query which tells us to add u to all elements in the range [l,r] then if I perform a point update and make X[l] = X[l] + u think what happens to RSQ[i] for different values of i.

RSQ[i] is unaffected for all i where i < l
and RSQ[i] = RSQ[i] + u for all i >= l.

Effectively we just did a range update on the abstract array RSQ and the range update is equivalent to adding u to all elements of array RSQ from l to N.

But we wanted the range update to be only for the range [l,r], so we should now do a range update in which we subtract u from [r+1,N] and this is the same as doing a point update to X[r+1] such that:

X[r+1] = X[r+1] — u

it must be easy to see the abstract array RSQ is nothing but the required SUM array.

So here is the algorithm :

 For every range update query (l,r,u):
   point_update(l,current_val + u)
   point_update(r+1,current_val — u)
 For every query -> value at pos idx:
   print SUM[idx] + V[idx] 

AC code : https://ideone.com/vBZpYx
Time complexity per query is logN.

Forest Queries

For every query of the form (x1,y1,x2,y2) we need to answer the number of trees inside the rectangle described by the top left cell of rectangle (x1,y1) and the bottom right cell of rectangle (x2,y2).

Define : DP[i][j] as the number of trees in the rectangle described by (1,1) and (i,j).

Can we use DP matrix to evaluate answers for every query?

Ok, but how?

How to build DP matrix?
Let tree[i][j] = 1, if there is a tree at cell (i,j) else tree[i][j] = 0.

 DP[0][0] = DP[-1][0] = DP[0][-1] = 0
 for i from 1 to N:
    for j from 1 to N:
     DP[i][j] = DP[i-1][j] + DP[i][j-1] — DP[i-1][j-1] + tree[i][j] 

Time complexity for build O(N*N) and time complexity per query is O(1).
AC code : https://ideone.com/5dGTfY

Hotel Queries

Observation : For each group, we need to find the 1st hotel with enough vacancies and book rooms for the group in that hotel.

Brute force : Start checking every hotel from left to right for the number of rooms it has. As soon as you find a hotel with enough rooms use required number of rooms in this hotel. Repeatedly do this till all groups have been assigned a hotel.

How do I know if there is any hotel in the first x hotels which can be assigned to the current group?

Algorithm :

 For each group gi with size si:
   Find the 1st hotel x such that vacancy(x) >= si.
    Do point update : vacancy(x) = vacancy(x) — si.
    Print x.
   If no valid x exists print 0.
 

Time complexity is O(Mlog^2N), logN steps for the binarySearch and each step of the binary search uses the Range max query segment tree which works in logN time.

List Removals

Brute force is quite simple if you simply simulate what is mentioned in the problem.
Let us try to optimize. So whenever we are asked to delete some xth element of the list we need to first locate the xth element, print it and then delete it.

How can we make the above processes faster?
Let us keep a boolean array PRESENT of size N and PRESENT[i] = 1 if the ith element of the list has not yet been deleted, 0 otherwise.

Now let us say we have the query : delete the xth element of the list, then this means we are going to delete the element at the jth index of the initial list such that :

1. PRESENT[j] = 1.
   
2. sum of PRESENT[i] for all i from 1 to j = x.

Why above conditions are necessary and sufficient to locate the correct element?
If are we deleting the element it has to be present in the list currently and so PRESENT[j] should be 1.
If this element at index j(of the initial list) is the xth element of the list(current state of the list) then there are exactly x elements present in the list in range [1,j](of the initial list) and remaining j — x elements got deleted in some previous queries.

How do I find this j?

Ok, elaborate.

How do I find number of elements not yet deleted in the range [1,j]?

Once you have found the correct j, you need to print it and also mark PRESENT[j] = 0 and make the required point update in the segment tree.

Time complexity analysis is similar to previous problem.

AC code : https://ideone.com/anpuXy

Salary Queries

Okay so, this seems a bit hard. Maybe if the max possible salary of the employees was limited to some smaller amount(instead of a billion) we might be able to solve it.

So try solving the problem under the constraint that p,a,b <= 10^7.
Now the problem is much easier if I maintain the number of people with a given salary, let us define
freq[i] : number of employees with the salary i
We may now build a range sum query segment tree on this array and to answer a query we simply calculate the sum of the range [a,b].

For updating the salary of some employee from x to y, we do the point updates freq[x] -= 1 and freq[x] += 1 because now 1 less employee has salary x and 1 more employee has the salary y.

But the problem is not solved, since we needed to do this for max possible salary = 1billion, but now we know how to do it for 10^7.

So lets group the salaries into 10^7 buckets and each bucket represent a range of 100 different contiguous salary values. The 0th bucket represents salaries from 1 to 100 and ith bucket represents the salaries from (i)*100 + 1 to (i+1)*100.

These buckets will store aggregated number of employees that have salaries in the given range represented by the bucket.

Now for query [a,b] : all the buckets that are entirely in the range [a,b] their aggregate values should be taken and summed up and for the 2 partial buckets(or 1) not entirely included in the range [a,b] we shall do a brute force.

So build a segment tree over the buckets and calculate the sum over all completely included buckets in the range [a,b]. For remaining partially included buckets do a brute force(actually iterate over approx 100 possible values and choose to include those which are required by a particular query, refer code).

A code will make this explanation much more clear.

AC code : https://ideone.com/zg97c8

other way to do it is using a dynamic segment tree in which you only build a node of the tree when it is needed.

Distinct Values Queries

This is a direct application of the MO's Algorithm. You may read more about MO's algorithm on https://blog.anudeep2011.com/mos-algorithm/

The brute force can be done by simply iterating from index a to b and maintaining number of distinct elements seen till now and a frequency array to indicate which elements and how many occurrences of those elements is present.

Frequency[i] = count of occurences of i in the current range.

Next we try to build the required ADD and REMOVE functions which help MO's algorithm to function properly.
To ADD a new element in the current range simply check if this element is already present(frequency > 0) and if it is present just increase its frequency else if its frequency was 0 then make it 1 and also increase the number of unique elements in the range.
To REMOVE an element from the current range, decrement its frequency by 1, if its frequency reaches 0 then decrease the number of distinct elements in the current range.

After this sort the queries as described by MO's algorithm and you are done.

Twist : We cannot use frequency array as value of individual element can go upto 10^9. So what I'll simply use an unordered_map?

No, unordered_map solution will time out due to high constant factor involved.

Time complexity : O((N+Q)root(N))

AC code : https://ideone.com/RkC547

Subarray Sum Queries

Let us try to keep track of the max sum subarray in a particular range [L,R]. If we were to build a segment tree in which each node of the tree stores max sum subarray of the range that the node is responsible for then the root keeps track of max sum subarray in the range [1,N].
However for segment trees to be efficient we need to generate the answer of interior nodes of the tree using the answers/information provided by the child nodes.

Now let's try to generate the answer for some interior node P of the segment tree assuming that we already have the answers for the children of the node P.

Node P is responsible for the range [l,r], its left child is responsible for the range [l,mid] and its right child is responsible for the range [mid+1,r].

Now we need to find the sum of max sum subarray in the range [l,r].
Assume you have all necessary information about the child nodes but if you have some information about a child node you also need to generate that piece of information for the parent node as well(since this node also has a parent which will use information given by P to generate it's answer).

So to summarize, for every node which represents the range [l,r] we should store :
1. sum of max sum subarray in the range [l,r].
2. maximum possible sum of some prefix [l,x] (such value of x is chosen, such that l <= x <= r and sum of elements in range [l,x] is maximum possible.)
3. maximum possible sum of some suffix [x,r].

We now know how to calculate sum of max sum subarray for some node using the above mentioned information about children nodes but as discussed we should also calculate prefix and suffix info for the parent also.

Refer the combine function in the code for more clarity.
AC code : https://ideone.com/MhVmBs

Time complexity : logN per update.

Forest Queries II

Problem is almost the same as Forest Queries but we also have point updates.
I will discuss two approaches, one of them is quite efficient while the other one struggles to run in the time limit(passes if constant factor is low).

Approach 1

Let us do build the same DP matrix which we had built for the problem Forest Queries. If somehow we are able to keep our DP matrix consistent with the updates then our answer will be the same as before.

ANSWER TO QUERY (x1,y1,x2,y2) : DP[x2][y2] — DP[x1-1][y2] — DP[x2][y1-1] + DP[x1-1][y1-1]

How to efficiently track the updates that happen on some entry DP[i][j]?

Alright, so now I need to efficiently add or subtract 1 from all the matrix entries (x,y) where that x >= i and y >= j.

Time complexity O(Q*N*logN)
AC code : https://ideone.com/mcAdwL
Code for fenwick tree is taken from : https://cp-algorithms.com/data_structures/fenwick.html

Approach 2
This approach is more efficient and some might also find it easier to understand.
It uses a 2D Binary Indexed tree to achieve an overall time complexity of O(N^2 + Q*log^2(N)).

You can read more about it here : TopCoder-2DBIT

Range Updates and Sums

No surprises here. My solution will use the data structure and the technique related to that data structure which most would have already guessed after reading the problem statement. The important thing would be a thorough understanding of the concept and a neat implementation(I have tried to make it readable).

Alright so our segment tree needs to support the following operations :
1. increase values in range [l,r] by x.
2. set values in range [l,r] = x.
3. return sum of values in range [l,r].

Think about what information should we store per node of the tree, so that we are able to lazily update our nodes when a new update comes in and we are able to propagate the updates downward when needed.

To better understand lazy propagation, I recommend reading this : Super amazing theory in 1 comment (My implementation uses applyAggr and compose functions mentioned here).

Time Complexity is logN per query.
If something is not explained or if something isn't clear feel free to ask but I recommend understanding lazy prop well before attempting the problem or reading the editorial.
AC code : https://ideone.com/8HQxMk

Please feel free to point out mistakes, suggest better/alternate solutions and to contribute.
I'd be glad to know if this helps :)

P.S. Will add remaining problems in a few days.

UPD : Editorial is almost complete with 2 problems left. 2nd last uses segment tree with lazy prop and I am guessing the last one uses some kind of persistent data structure, will add soon.

I have been recently working on preparing libraries for commonly used data structures in competitive programming.

here is a link to the code : https://github.com/kartik8800/segTree

The above segment tree library should (according to me) work for a huge number of range query problems with point updates.

The things you need to specify to declare a segment tree is a function combine that tells the tree how to combine the results of child nodes to form parent node, an array for which the tree is to be constructed and a value such that combine(x, value) = x.

Here are a few examples:

vector dataVector = {5, -8, 6, 12, -9};

int small(int x,int y){return min(x,y);}
SegmentTree < int > rangeMinQueries(dataVector,INT_MAX,small);

int sum(int x,int y){return x+y;}
SegmentTree < int > rangeSumQueries(dataVector,0,sum);

long long product(long long x,long long y){return x*y;}
SegmentTree < long long > rangeProductQueries(dataVector,1,product);

also have a look at the following solutions to popular SPOJ segment tree problems:
solution to SPOJ GSS1 using segTree library : https://ideone.com/EFxf6O
solution to SPOJ KGSS using segTree library : https://ideone.com/fUK5Jz

I wonder if it is possible to provide a similar implementation of the segtree with lazy propagation, would be amazing to receive help with that.
It would be great to know if people find this helpful and also check out implementations of other commonly used data structures like tries, DSU, minQueue and more.

UPD: made a video explaining the usage and features https://youtu.be/K-86mKNAsmU