THOUGHTS OF A DEBUGGER

  Once again I have came with the topic which is very useful for optimization in hard problems or the only trick to be used in small problems to get AC. Learning this trick in initial stages will be very helpful. Problem statement Given an array of size N initialized with all 0's. Given M queries where each query consist of three values(a,b,c), where you have to increment all the index between a and b(inclusive) with c. After processing all the queries, print the array. Simple solution which takes O(N * M) Here we will run a loop from a to b each of m time and increment that indexes with c. If N and M is greater than 1,000, this approach will surely get timeout. Optimized Solution in O(N+M) Once thing we must notice here is that we do not need to print the updated array after each query. We can preserve the queries and atlast updated the array all at once with those m queries. We can use a value accumulator which sweeps over the array and update each and every inde...