You are not logged in. Please login at www.codechef.com to post your questions!

×

Disjoint Sparse Table

3
2

While solving NOV17 SEGPROD I stumbled upon this comment on codeforces. Talking about a Data Structure like Sparse Table that can answer range sum query in $\theta(1)$. But the comment only talked about how to answer query in $\theta(\log n)$.

Though my naive implementation of the $\theta(\log n)$ approach did solve the problem without requiring many optimizations. I was wondering if anyone has heard of this DS before and knows the approach to solve it in $\theta(1)$.

asked 14 Nov, 02:26

nilesh3105's gravatar image

4★nilesh3105
2566
accept rate: 18%

edited 14 Nov, 02:28


During the competition I had come up with the same solution as the one you have mentioned. The basic idea of the DS: Define M to be the midpoint of the array. 1/2 of all possible queries would be such that its Left endpoint is before M and its right endpoint is after M. So it would be efficient to keep prefix products from M to all other indices(even the ones before M). Any query which has a Left endpoint on the left of M and right endpoint on the right of M can be easily answered in O(1) using this prefix. Now the idea is to recursively do the same thing for the left and right half separately. That's why memory and pre-processing takes Nlogn time/mem.

This DS can subsitute anything a segment tree can do but in O(1) time. However, it takes more memory and doesn't support updates.

My code: https://www.codechef.com/viewsolution/16141888

link
This answer is marked "community wiki".

answered 14 Nov, 13:13

adhyyan1252's gravatar image

6★adhyyan1252
825
accept rate: 8%

If I understood this correctly, then you have to find some index (whose precomputation has already been done)and for any query, you have to find an index which lies inside the query and take the prefix product and also the ("suffix ") product . ?

(14 Nov, 13:43) gagan86nagpal5★

Exactly what I was looking for! I have couple doubts though. Why did you use $size = 2^{\lceil \log n \rceil}$ and not $size = n$. Also how did you find required level $lev = \lceil \log n \rceil - \lfloor \log l \oplus r \rfloor - 1$

(14 Nov, 15:41) nilesh31054★

Do you have link to a tutorial on same?

(14 Nov, 15:54) nilesh31054★
1

@gagan86nagpal and @nilesh3105 you both are right. I think finding the index/level is the hardest part in this technique and it took me the longest time to figure out how to do it in O(1). I rounded the size up to the nearest power of 2, because then all the mid points are like this: Lev 0- 1000, Lev 1- {0100, 1100}, Lev 2- {0010, 0110, 1010, 1110} etc. Now by intuition I came up with a solution which can find the level in O(1). Define A = L XOR R. The most significant bit of A will tell you the level. C++ has a function which hopefully runs in O(1) to find the MSB, which is __builtin_clz()

(14 Nov, 19:40) adhyyan12526★

@nilesh3105 I dont think there is any tutorial on this kind of DS. I dont even know what to call it.

(14 Nov, 19:41) adhyyan12526★

Kudos to you man.

(15 Nov, 00:19) gagan86nagpal5★

@adhyyan1252 you can read @hemanth_1's comment here. This technique is a special case of centroid decomposition :D

(15 Nov, 18:18) meooow ♦5★
2

So I figured out a formal proof for $l \oplus r$ formula. Anyone interested in a full fledged tutorial on this DS?

(yesterday) nilesh31054★

@nilesh3105 why not!

(yesterday) c_utkarsh5★
showing 5 of 9 show all

nilesh3105 ,did you find range multiplicationn by segment tree ?

link

answered 14 Nov, 04:13

anarboss's gravatar image

3★anarboss
1
accept rate: 0%

No I did not. I don't think you can optimize segment tree enough to solve this problem. I used a different data structure which is a bit like segment tree and a bit like sparse table.

(14 Nov, 15:46) nilesh31054★

Hi nilesh3105, I also tried a sparse table approach but couldn't able to manage all subtasks. Can you share your optimizations (if any)?

link

answered 14 Nov, 07:13

gagan86nagpal's gravatar image

5★gagan86nagpal
9115
accept rate: 14%

I also couldn't solve it using sparse table. Though by switching index of sparse table from $[N][\log N]$ to $[\log N][N]$, using bit shift instead of dividing, not storing temporary variables and let compiler handle optimizations I saw a significant improvement in running time. Probably with some optimizations around % operator it could pass

(14 Nov, 15:51) nilesh31054★

Yeah its right. % operator is too costly. I got 20+ submissions before I realized this fact. When number of queries is too high use mod efficiently. Cost of if<<Cost of %.

(15 Nov, 09:11) soham12345★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,132
×253
×27
×13

question asked: 14 Nov, 02:26

question was seen: 429 times

last updated: yesterday