Heaps and Priority Queue

Contents:

1. Heaps and Priority Queue
2. Types of Heap
1. Min-heap
2. Max-heap
3.  Some uses of heap with their complexities.
4.  Problem from Hackerearth:
1. Brute Force solution
2. Solution using priority_queue

Square Root Decomposition with range updates

Hello guys! Hope you all are doing well.

In Codechef December challenge I came across a very interesting problem which can be solved using square root decomposition. So i am gonna explain the algorithm using that particular problem. Link to problem.

Pre-requisites: properties of XOR operation.

Lazy Propagation on segment tree

LAZY PROPAGATION

This is for the update query in the minimum range query question.The brute force method involves
various updates in the segment tree for just one query.However ,in lazy propogation,the update is
only propogated to the child nodes as and when it is required i.e. we maintain another array which
keeps the track of all the previous updates which have not been made yet in the segment tree and
will update only when there is a query on that particular range.

Segment Trees and range minimum query

SEGMENTED TREES

We generally come across question involving range queries and update queries which may or may not require to print output after each queries.
For example:-we have an array arr[0.....n-1] and following two queries:
1.find minimum in range [l,r] where 0<l<r<n and output it.
2.upadate each value in range [l,r] and output the new array.