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>

Bishal Gautam