Qualified's blog

By Qualified, history, 7 weeks ago, In English

You are given a number $$$n$$$ and a number $$$m$$$ and an array $$$a$$$ of $$$n$$$ numbers and 2 types of queries. All of the numbers below are 0 based indexing.

1) Given 3 numbers, $$$l, r, x$$$. You add all the numbers from $$$l$$$ to $$$r$$$(inclusive) by $$$x$$$. For example if the initial array was {5, 4, 3, 9, 2} and the query was {0, 2, 5} then the array would become {10, 9, 8, 9, 2}

2) Given 1 number $$$y$$$, output $$$a[y]$$$. This should be self explanatory.

At the end print the array $$$a$$$.

$$$m$$$ describes the number of queries being asked.

Example:

4 3
1 9 2 2
2 2 3
0 3 5
2

Output:

10
6 14 10 7

Should be less that $$$O(n^{2})$$$

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

»
7 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Segment tree?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't SegTree for finding the sum of numbers in a range? Am I stupid?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, SegTrees are for that. For the first query just use Lazy Propagation, for the second your range is l = r = y.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Amazingly enough, you don't even need lazy propagation. You can just swap the logic in the update and query function. Update adds a value to a set of nodes, and query accumulates values as it moves down from the root to the leaf.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Consider a segment tree on the "change in value" so we can use the so called "+1/-1 trick" and if we want to increment [L, R] by X, we can increment L by X and R+1 by -X