Qualified's blog

DS that does 2 queries
By Qualified, history, 4 years 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

Comments Comments (5)
| Write comment?
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Segment tree?

→ Reply
  • »
    »
    4 years 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?

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply