All Tracks Data Structures Trees Binary/ N-ary Trees Problem

Tree Queries
Tag(s):

Binary Tree, Easy

Problem
Editorial
Analytics

There is a complete Binary tree in which there are N nodes. Each vertex of the tree is assigned a value.

You are given the values of all nodes in level order traversal of the binary tree (from left to right).

You are given three types of queries.

1 X  LV  Find the value of Xth node from left on the level LV.

2  L R  Find the the sum of values of nodes from level L to R (L and R are inclusive). 

3  X  LV  VAL Update the value of Xth node from left which is at level LV to VAL

Note: Root is at level 1.


INPUT

In the first line you are given two integers N, Q.

In the next line you are given an array A where the ith value denotes the value of ith node.

In the next Q lines you are given one of the three queries.

It is guaranteed that there exists at least one query of type 1 or 2.

Also it is guaranteed all given queries are valid.


OUTPUT

For each query of 1st and 2nd type print the required value.


CONSTRAINTS

\(1 \leq N \leq 2*10^{6}\)

\(1 \leq X \leq 10^{6}\)

\(1 \leq L \leq 21\)

\(1 \leq Q \leq 10^{6}\)

SAMPLE INPUT
5 3
2 1 3 4 2
1 2 2
3 2 3 5
2 1 3
SAMPLE OUTPUT
3
15
Explanation

In the First query you have to find the 2nd node at level 2 which is 3.

In the second query you have to update the 2nd node from left at level 3.

So new array looks like 2 1 3 4 5

In last query you have to find the sum of  values of all nodes from level 1 to 3.

so 2 + 1 +3 + 4 +5=15.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?