Hd7's blog

Help me know this technique!!!
By Hd7, history, 5 years ago, In English

I read many people's solutions and I realized the technique that helps me count effectively. This technique is:
If i want to increase all elements in range $$$[l;r]$$$ in array $$$cnt[]$$$, i will set $$$cnt[l]++$$$ and $$$cnt[r+1]--$$$, after that i will calculate cumulative sum from left to right, $$$cnt[i]+= cnt[i-1], \forall i \in [1:n]$$$.

The same approach is applied for 2d counting arrray. If i want to increase every cell in rectangle with top-left $$$(x_1, y_1)$$$ and bottom-right $$$(x_2, y_2)$$$. I will set
cnt[x1][y1]++; cnt[x1][y2+1]--; cnt[x2+1][y1]--; cnt[x2+1][y2+1]++; and then calculate the partial sum of this 2d counting array.
I want to get more information for this technique. Could you help me the name of it or any link that is relevant. Thanks in advance.

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

I don't think there's a specific name for it. But, you build a difference array. This technique is mentioned in Competitive Programmer's Handbook.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Is the book written by Antti Lâksonen? Omg i have downloaded it before, is this technique in advance chapter that i have not covered yet?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      It's on page 93, under Range Updates.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Thank you very much!!

        → Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

This is just prefix sum

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Prefix sum is the work after we set ++, —-. I want to know more about the origin of this technique.

    → Reply
»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

I don't know its name either. I often call it difference array($$$b_i=a_i-a_{i-1}$$$). If $$$b$$$ is $$$a$$$'s difference array, then $$$a$$$ is $$$b$$$'s prefix sum array.

We can do lots of things with it.

For example, a classic problem, you are given an integer sequence $$$a$$$ with length $$$n$$$, then following $$$q$$$ operations, either add a number to $$$[l,r]$$$, either query the GCD of $$$[l,r]$$$. If we consider $$$a$$$'s difference array $$$b$$$, then the first operation is quite easy. For the second operation, $$$\gcd(a_l,a_{l+1},\dots,a_r)=\gcd(a_l,a_{l+1}-a_l,\dots,a_r-a_{r-1})=\gcd(a_l,b_{l+1},\dots,b_r)$$$. Just build a segment tree of $$$b$$$, every time calculate $$$a_l$$$ and $$$\gcd(b_{l+1},\dots,b_r)$$$.

For another example, 1110E magic stone. See more in the editorial. It's kinda beautiful.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thank man a lot, i will try it.

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

It's just common sense for a considerate amount of coders. Don't need to think so hard about it, you've got a mind-blow experience.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I see it so magical, i want to get more insights on it. Why do you say that? That I don’t understand clearly something makes me discomforts

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

You can also consider a[l]++, a[r+1]-- as add[l]++, remove[r]++ (maybe it's better for understanding)

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

It's called Mars' Trick in Romania

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please provide link to the explanation how it works?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This technique is very interesting, I got problems many times that solved by this, like in my online assessments.

→ Reply