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.
  1. Practice
  2. Data Structures
  3. Arrays
  4. Array Manipulation
  5. Discussions

Array Manipulation

  • nivdatta88 + 3 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,

          	  ARR						DIFF
(5,3)  0    0    0    0    0		0    0     0    0
(1,2)  100  100  0    0    0		0    -100  0    0
(2,5)  100  200  100  100  100		100  -100  0    0
(3,4)  100  200  200  200  100		100  0     0    -100

    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.

    • zeralight + 1 comment

      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]

    • julie_larson + 3 comments

      I think the DIFF matrix should be:

      0    0    0    0    0
100  0    0    -100 0
0    100  0    0    0
0    0    100  0    -100

      then x is 100+100+100-100-100 = 200

      still don't quite get it though

      • cse160001033 + 0 comments
        [deleted]
      • cyxingfa + 1 comment

        I think the Diff should like this

          0   0   0   0   0 
  100  0  -100  0    0  <--- 1 2 100, 3rd col is 100 less than 2nd col 
  100  100 -100 0    0  <--- 2 5 100, 2nd col is 100 more than 1st col
  100  100  0  0  -100   <--- 3 4 100, now 3rd is equal to 2nd, and 5th is 100 less than 4th col

        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

        • marc_ponchon + 0 comments

          Thanks this helps me to understand how it works.

      • feynman65 + 2 comments

        @julie_larson
        100+100+100-100-100 = 100 still not 200 I've been banging my head still not able to understand this solution.

        • filipetrm + 0 comments

          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:

          iteration		value of x	accumulated sum
0			0		0
1			100		100
2			100		200	
3			0		200
4			0		200
5			-100		100

          The maximum value of the accumulated sum is 200.

        • joshumcode + 0 comments

          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.

    • nayeemnawaz93 + 0 comments

      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.