[CSES] Range Update Query

2021-06-23

2 minute read

Algorithm

cses , binary index tree

Range Update Query

Task:

Given an array of $n$ integers, your task is to process $q$ queries of the following types:

increase each value in range $[a,b]$ by $u$
what is the value at position $k$?

Input

The first input line has two integers $n$ and $q$: the number of values and queries.

The second line has $n$ integers $x_1,x_2,\dots,x_n$: the array values.

Finally, there are $q$ lines describing the queries. Each line has three integers: either "$1$ $a$ $b$ $u$" or "$2$ $k$".

Output

Print the result of each query of type 2.

Constraints

$1 \le n,q \le 2 \cdot 10^5$
$1 \le x_i, u \le 10^9$
$1 \le k \le n$
$1 \le a \le b \le n$

Example

Input:

8 3

3 2 4 5 1 1 5 3

2 4

1 2 5 1

2 4

Output:

5
6

Solutions:

Intuition:

It looks like we got a cyclic sort problem. Since the input array contains unique number from range $1$ to $n$, so we will try to place the numbers on their corresponding index. E.g: The position with index $0$ will hold the value $1$ and so on... Once we have the array with their value in its correct place, we can pass through the array to find out the index which does not have the correct value. And that is our missing number.

Implementation:

 1  def find_missing_number(nums):
 2    i, n = 0, len(nums)
 3    while i < n:
 4      j = nums[i]
 5      if nums[i] < n and nums[i] != nums[j]:
 6        nums[i], nums[j] = nums[j], nums[i]  # swap
 7      else:
 8        i += 1
 9 
10    # find the first number missing from its index, that will be our required number
11    for i in range(n):
12      if nums[i] != i:
13        return i
14 
15    return n
16

Analysis:

Time complexity: $O(N)$

Space complexity: $O(1)$

But we can do it leaner.
The input array will follows arithmetic progression, if it doesn't have missing number. Therefore, we can calculate the sum of completed array by sum formula of arithmetic progression. After that, the difference between aforementioned sum and input array's sum is our missing number. $$\sum\limits_{i = 1}^n {a_i} = \frac{n(a_{1}+a_{n})}{2}$$

Implementation:

1   def find_missing_number(nums):
2    n=len(nums)
3    return (int((n+1)*n/2-sum(nums)))
4

Analysis:

Time complexity: $O(N)$

Space complexity: $O(1)$