We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I still have some doubt if anyone could explain it. I understand that it is making use of difference array to keep track of the difference between items rather than updating every item.
However as I understand, size of difference array is one less than total items in the actual array.
However the logic used seems to be a variant of difference array that I am not able to understand. It would be great if someone could help me connect the dots from this difference array to the actual working solution of this problem. Thanks.
so finally, 1st col is always the real value, and others are accumlated of previous values and it self.
so actual values are 100 200 200 200 100, max is 200
As i have understood
(5 , 3) 0 0 0 0 0
(1 , 2) 100 100 0 0 0 -> first and second places i.e a=1,b=2 , k=100, now a+k = 0+100 = 100, b+K = 0+100 = 100.
(2 , 5) now from 2 to 5 i.e 2,3,4,5 are added with K i.e 100.
already 2=100 now 2 becomes 100+100 =200, simialrly 3 = 0+100=100,4=0+100=100,5=0+100=100.
(3 , 4) now 3 and 4 are added with 100.
ie 3 value is 100 it becomes 100+100=200, 4 becomes 100+100=200.
Array Manipulation
You are viewing a single comment's thread. Return to all comments →
I still have some doubt if anyone could explain it. I understand that it is making use of difference array to keep track of the difference between items rather than updating every item.
However as I understand, size of difference array is one less than total items in the actual array.
So as per the demo program given,
However the logic used seems to be a variant of difference array that I am not able to understand. It would be great if someone could help me connect the dots from this difference array to the actual working solution of this problem. Thanks.
Hello, I don't really get your DIFF representation, but here is the deal:
you need to keep in mind that at the end of queries to get the real value of i we need to sum the values of A[0]->A[i].
for a query (l, r, x) if we add x to A[l] then we're sure later for every k in [l, r] sums(0->k) will include x.
the problem is that every k > r will also include that x, therefore we'll decrement l[r+1] by x.
Now the sum through 0 -> k will include x only if k >= l and will exclude it only if k > r which is equivalent to:
sum(0->k) will consider x only if k is in [l, r]
I think the DIFF matrix should be:
then x is 100+100+100-100-100 = 200
still don't quite get it though
I think the Diff should like this
so finally, 1st col is always the real value, and others are accumlated of previous values and it self. so actual values are 100 200 200 200 100, max is 200
Thanks this helps me to understand how it works.
@julie_larson
100+100+100-100-100 = 100 still not 200 I've been banging my head still not able to understand this solution.
The final diff array should be like this:
100 100 0 0 -100 (straight foward from the code)
So when you iterate over it to get the accumalated sum you'll get this:
The maximum value of the accumulated sum is 200.
They're always checking the sum against the count, so when the sum is less than the count (which is the greatest sum so far) the count doesn't update.
As i have understood (5 , 3) 0 0 0 0 0 (1 , 2) 100 100 0 0 0 -> first and second places i.e a=1,b=2 , k=100, now a+k = 0+100 = 100, b+K = 0+100 = 100. (2 , 5) now from 2 to 5 i.e 2,3,4,5 are added with K i.e 100. already 2=100 now 2 becomes 100+100 =200, simialrly 3 = 0+100=100,4=0+100=100,5=0+100=100. (3 , 4) now 3 and 4 are added with 100. ie 3 value is 100 it becomes 100+100=200, 4 becomes 100+100=200.
among these 200 is max value.