DCP-427: Rotation and Summation Back to All Problems

Medium Data Structures > Binary Indexed Tree


You are given an array A of length N and Q queries of following types: 1 K : Rotate the array K steps to the Left. 2 K : Rotate the array K steps to the Right. 3 P X: Change the value of index P of current array to X 4 L R: Find the summation of array element from index L to R inclusive. Input: ------ Input starts with an integer **T (1<=T<=5 )**, denoting the number of test cases. Each case contains an integer **N (1 ≤ N ≤ 100000)** denoting the number of elements of array A. The next line will contain **N** integers separated by spaces, denoting the elements of the array A. Each of these integers will be non-negative integer not greater than **10^9**. The next line contain an integer **Q (1 ≤ Q ≤ 100000)**, then following Q lines contains queries of above mentioned types. Output: ------- For each case of input if the query is of type 4, print a line with summation. Constraints: ------- **1 <= N,Q <= 100000**<br> **0 <=K,P,L,R <=N-1**<br> **0<=X<=10^9** ***The indices are 0 based.*** Sample Input ------------ 1 5 1 2 4 3 6 7 4 2 4 1 1 4 2 4 2 2 4 2 4 3 2 5 4 2 4 Sample Output ------------- 13 10 9 12 ---------- **Explanation:**<br> Initially array is : 1 2 4 3 6<br> There are 7 queries to process.<br> 1st: Summation from index 2 to 4, 4+3+6=13<br> 2nd: Rotate 1 steps to left. so, array become: 2 4 3 6 1<br> 3rd: Summation from index 2 to 4, 3+6+1=10<br> 4th: Rotate 2 steps to right. so, array become: 6 1 2 4 3<br> 5th: Summation from index 2 to 4, 2+4+3=9<br> 6th: Change value at index 2 to 5. so array become: 6 1 5 4 3 <br> 7th: Summation from index 2 to 4, 5+4+3=12<br>


Problem Setter:

Bishal Gautam

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats

31/127

Solve/Submission

Ranking

# User Language Timing
01 feodorv C 0.10s
02 fire_tornado Cpp 0.20s
03 tariqiitju Cpp14 0.20s
04 Sarwar05 Cpp 0.25s
05 SakibAlamin Cpp14 0.28s
06 pulak_ict_mbstu Cpp14 0.32s
07 muradhossen Cpp 0.33s
08 emrul Cpp14 0.33s
09 shahjalalshohag Cpp14 0.33s
10 Ramprosad Cpp 0.34s
11 refatul_fahad Cpp14 0.34s
12 Turin Cpp 0.38s
13 snow_man Cpp14 0.38s
14 Nobel Cpp 0.39s
15 Bappy Cpp14 0.40s
16 ksohan Cpp 0.41s
17 sayedgkm Cpp 0.47s
18 badassiumoxide Cpp 0.49s
19 anik_JU Cpp 0.49s
20 _c_k_r_ Cpp 0.51s
21 mahbubcseju Cpp 0.55s
22 Taran Cpp14 0.69s
23 AmdSadi Cpp 0.70s
24 shamimjucse Cpp 0.71s
25 mh755628 Cpp14 0.72s
26 shahadat191 Cpp 0.88s
27 Jisancse Cpp14 0.95s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support