Array and queries
Difference between en1 and en2, changed 73 character(s)
Given an array of N integers, you are given two types of queries:-↵
#### Type 1 ::: x y ↵
Append y after index x (array size increases by 1 after every type 1 operation )↵
#### Type 2 ::: print↵
Print the array ↵
↵
### What is the efficient way to solve this problem?↵
↵
Type 2 query takes O(n) time.↵
↵
So the problem can be solved in O(n^2).↵
↵
If we are given information that there are many many operations of Type 1 than Type 2 can we reduce the complexity?↵
↵
For example, if we are given that Type 2 operations are <= sqrt(N) or so?↵
↵
Thanking you.↵
↵
UPD: Suppose if the query is like find the maximum in [l,r] range etc↵
↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English RNR 2017-12-18 21:37:38 73
en1 English RNR 2017-12-14 07:20:41 577 Initial revision (published)