Taking square root with segment tree

Revision en6, by RubenAshughyan, 2019-02-26 21:35:42

Hi everyone. Today I encountered a data structures problem, which is a slight swist on standart segment tree problem.

You are given an array A of size N. N ≤ 10^5, A[i] ≤ 10^6, You need to process 3 types of queries

  1. Print the sum of all integers ai where L ≤ i ≤ R.

  2. Add x to each integer ai where L ≤ i ≤ R.

  3. For each integer A[i] where L ≤ i ≤ R, replace it with floor(sqrt(A[i])). Where sqrt(a) is the square root of a, and floor(b) is the integer value of b after removing everything on the right of the decimal point.

There can be Q≤20000 queries.

If we didn't have type 3 query, then we are left with standard lazy segment tree problem.

How to handle 3rd type queries?

Tags #advance data structures, #data structure, #help, howto

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English RubenAshughyan 2019-02-26 21:35:42 3 Tiny change: 'day I enconted a data ' -> 'day I encountered a data '
en5 English RubenAshughyan 2019-02-26 21:32:08 2 Tiny change: 'i everyone,\nToday I ' -> 'i everyone.\nToday I '
en4 English RubenAshughyan 2019-02-26 21:31:43 37
en3 English RubenAshughyan 2019-02-26 21:30:28 13 Tiny change: '. _N ≤ 100000, A[i] ≤ 1000000,_\nYou ne' -> '. _N ≤ 10^5, A[i] ≤ 10^6,_\nYou ne'
en2 English RubenAshughyan 2019-02-26 21:29:54 8
en1 English RubenAshughyan 2019-02-26 21:29:03 737 Initial revision (published)