SOLVE

LATER

Tree Queries

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 1^{st} and 2^{nd} 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}\)

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

Initializing Code Editor...

{"416d543": "/pagelets/problems-hint/algorithm/tree-queries-45/", "7d6c875": "/pagelets/recommended-problems/algorithm/tree-queries-45/", "05bc839": "/pagelets/show-submission/algorithm/tree-queries-45/", "91f3d9c": "/pagelets/problem-author-tester/algorithm/tree-queries-45/"}

realtime.hackerearth.com

80

e028c7b74d70a4aedf0597a46d59e927f90ce3b2

58a29e5cae2309f04b28

/realtime/pusher/auth/