Apptica

Range query problems are generally solved by either Binary Indexed Tree or Segment Tree. But sometimes when total queries are very large then you need some another data structure such that query time is almost constant and prefetching or pre-processing time is \(N log (N)\). The data structure is Sparse Tables. Assume a range query problem where \(10^7\) queries will be asked. Problem Statement :  You are given an array of size \(10^5\) and \(10^7\) queries to find the minimum of all the numbers in range \([L..R]\) then segment tree will be too slow, so we need something very fast. In sparse table we use the concept of binary numbers (Binary Lifting to be specific). The concept is to break down the complete linear array in chunks of powers of 2 and then utilize them to solve the queries. For example - let array indexes be \(0,1,2,3,4\) then break the array in chunks of powers of two as below - \(Row_0 : [0..0], [0..1], [0..3]\) \(Row_1 : [1..1], [1..2]...

How does it feels making copy of your coding templates before any coding competition ? Isn't there any method such that if you are making a new c++ file or c file and your template is automatically loaded. It is not a very tough task to just copy your code from github or just make copies of a template file but still here i am going to discuss a one time method so that you don't need to prepare anything before writing your code . An auto command such that your template is automatically imported whenever you make a new file is just awsome. Before we proceed i would like to say that every software or program you use certain events are associated with it. For Vim or any editor opening a file when it does not exist , opening a pre existing file etc. are different events. We need an autocommand for the former one. Vim contains a configuration file which can be edited from the home direcory as gedit .vimrc or vim .vimrc . You have to edit this file to make it perfect for codin...