How to apply segment tree when you have a modifiable array.

Revision en1, by 444iq, 2019-09-07 11:03:09

The question is you are given an array A of N integers N<=10^5 and q queries, q <= 10^5.

The are for types of query operation.

  1. 0 x y --> find the sum in the range x to y , 0 based index.

  2. 1 x --> Append element with value x to the end of array.

  3. 2 x ---> Delete element at index x, all the elements from x+1 to n-1 index comes forwards.

  4. 3 x y --> Change A[x] to y.

You have to return answer for all sum queries, that is query 1.

How to solve such problem.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English 444iq 2019-09-07 11:03:09 545 Initial revision (published)