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 index.
Let me simplify one query by breaking it into two parts. For an instance, think of only a, by a it means that every element with index >= a will be incremented by c. So, we increment arr[a] by c. Now, we need to use a destructor so that when the index == b+1, it will cancel the effect of the particular query. We can use subtraction as the destructor of addition. So we decrement arr[b+1] by c. After all those M updates, we run a loop from start to end of array and also keeping a value accumulator which gets updated index and index and the value of that particular index is equal to that of accumulator. Here's the code, that will make you understand easier.
#include< stdio.h>
int main() {
int N,M,a,b,c,i,acc=0,arr[100009];
scanf("%d %d", &N, &M);
memset(arr, 0, sizeof(arr));
while(M--) {
scanf("%d %d %d", &a, &b, &c);
arr[a] += c;
arr[b+1] -= c;
}
for(i=0;i< N;i++) {
acc += arr[i];
arr[i] = acc;
printf("%d ", arr[i]);
}
return 0;
}
This approach can be used similary for multiplication(here the destructor will be division) and XOR(here destructor will be itself XOR as A ^ A == 0) and nearly everything which comes with a destructor.