MIPT, camp 2014, day #3

Theme: data structures

sqrt-decomposition, semiplanes intersection
November 14, Sergey Kopeliovich

1 Sqrt decomposition
Consider searching substrings 1 , 2 , . . . , of equal length in the string . For each we are
interested, if is a substring of . We can solve this problem in linear time, in ( + ||) time, using
hash table of polynomial hashes of the strings . Here you may ask, why don't we use Aho-Corasic?
Let imagine, we just do not know this algorithm, but already heard about hashes and hash tables.
Let we have strings of arbitrary lengths. How to upgrade our solution to previous problem? The
idea of sqrt decomposition
length of all strings as then we may

helps. Let denote summary

in
time
(
+
||
)
.
Moreover
we have at most ( ) strings of
iterate lengths less
than

length at least , so summary worktime of solution "group string by length and proceed each
length in linear time" is also ( + || ).
You may use this approach not only string problems. For example, consider problems
about trees.

Let we have
It may contain a lot of vertices of degree less than , but there are
tree of vertices.
at most vertices of degree .

2 Sqrt decomposition on array

Consider an abstract problem "we have an array and want to proceed many dierent hard
queries on its subsegments". Let start with the simplest problem. Query #1: sum on the segment.
Query #2: change []. Let denote data structure which can proceed the rst type queries in time
() and can proceed queries of the second type in time () as [ (), ()]. For example, segment

tree as well
as
Fenwick
tree
is
[(log
),
(log
)]
data
structure.
Below
we'll
describe
[(1),
(
)]

and [( ), (1)] data structures. Denote = .

Solution #0. Note, we may calculate partial sums of initial array sum[i+1]=sum[i]+a[i], sum
on the segment [, ] is equal to sum[r+1]-sum[l], and during changing any [] we may simply
recalculate all the array sum[]. Another way is do not precompute anything, we may calculate sum
on the segment in linear time. These are solutions in [(), (1)] and [(1), ()].
Solution #1 in [(), (1)]. Let maintain array , [] is equal to sum of [] for [..( + 1)).
Query "sum on the segment": the segment can be viewed as head + body + tail, where body consist
of big parts whose sums we already know. Head and tail are not longer than . Query "change []":

set(i,x) { s[i/k] += x-a[i]; a[i] = x; }

Solution #2 in [(1), ()]. Let maintain the same array , and partial sums on it. Moreover let
maintain partial sums for each segment [..( + 1)). To change [] we have to fully recalculate two
1/5

arrays of partial sums (sums of small part, sums of ). To get sum on the segment, we may view it
as head + body + tail. For each of three parts we may get the sum in (1) time.
Solution #3 in [(), ()]. Let maintain partial sums sum[i+1]=sum[i]+a[i] and array of
changes, which have been applied to array since partial sums were calculated. Denote with array
as . One change is pair , . It denotes operation a[i]+=x. Let maintain property
|| . Query "sum on the segment": sum on the segment [, ] in initial array was equal
to sum[r+1]-sum[l], in (||) time we may calculate, how much it was changed. Query
"change []": to set [] := , let add to the pair , [], and put into []. If now
|| > then build partial sums of current version of the array in time (), and clear the
list . Let denote this operation . Note we'll call
not so often. One time per
queries. So amortized time of proceeding one query is ( ) = ( ).
Last approach we'll call delayed operations. This approach has no advantages solving this task.
But it will be useful later.

3 Sqrt decomposition on array: split & rebuild

Let solve more complicated task: we have four operations with the array
1. Insert(i, x)  insert on -th position.
2. Erase(i)  erase -th element of the array.
3. Sum(l,r,x)  calculate sum of elements greater than on the segment [, ].
4. Reverse(l,r)  reverse the segment [, ].
To solve this problem, at rst, let answer to query Sum(l,r,x) (the only query with some answer),
applied to all the array, ie query Sum(0,n-1,x). Let we have no other types of queries, only the
queries of type Sum.
So we can easily maintain sorted array and partial sums on it. To get answer to query let do
binary search and get sum on the sux. The time to build the structure is ( log ), the time to
answer one query is (log ).
Let solve full version of the problem. We have the array [0..). We will maintain some partition of
the array into segments = [1 , 2 , . . . , ]. For each segment we store
two versions initial and
and < 3 . Initially
sorted with partial sums. We
will
maintain
two
properties:

:
|
|

let split the array into = segments of length . For each of segments we'll call operation
Build which sorts the segments and calculates partial sums. The time spent for each segment is

log Now let describe the main operation Split(i), which returns such , that -the element is
the beginning of -th segment. If is not any beginning, nd = [, ), such that < < , and
split it into two segments = [, ) and = [, ). For segments and call Build, we've got new
partition of the array into segments: = [1 ,
2 , . . . , 1 , , , +1 , . . . , ]. Time to proceed

one Split(i) is () + (build( )), means if = time is log . Here we assume stores not
the segments, but links to it, so to "copy" segment we need only (1) of time. We have Split(i).
Now let express all other operations in terms of Split(i).

vector<Segment*> T;
int Split( int i ) { ... }
2/5

void Insert(i, x) {
a[n++] = x;
int j = Split(i);
T.insert(T.begin() + j, new Segment(n-1, n));
}
void Erase(i) {
int j = Split(i);
split(i + 1);
T.erase(T.begin() + j);
}
int Sum(l, r, x) { // [l, r]
l = split(l), r = split(r + 1); // [l, r)
int res = 0;
while (l <= r)
res += T[l++].get(x); // binary search and use partial sums
return res;
}
To proceed queries of type Reverse, we need to store additional ag "is the segment reversed",
implementation of Split(i) becomes bit more complicated, all other parts stay the same.

void Reverse(l, r) {
l = split(l), r = split(r + 1);
reverse(T + l, T + r)
while (l <= r)
T[l++].reversed ^= 1;
}

proceeding of each query may increase

We have the solution, which starts with = segments,
by at most 2. After queries it may happens, that 3 (three times bigger), at thismoment

= log .
let rebuild all the structure in ( log ) time. Amortized time ofone rebuild is log

In total our solution can proceed any query in amortized time ( log ).
We may speed up it. Note, Split(i) may be done in linear time, more precisely ( + ), rebuild

may be also done in liner time, in (). So let number of segments is equal to / log , amortized
time to proceed one query of type Sum is (++), where  time of Split(i), is equal to ( +),
 time of inner for-loop of function
Sum, is equal to ( log ),  amortized time per one rebuild,

is equal to ( ). In total we get ( ) per query.

4 Semiplanes intersection
Let solve one complicated problem acm.timus.ru:1390. The statement is: we stay on the plane at
point (0, 0). From time to time walls appear on the plane. The walls are segments do not containing
(0, 0). The walls may intersect each other. From time to time we launch the bullet. The bullet ies
3/5

in a straight line, while does not touch a wall. Answer to launch-bullet-query (type = "bullet") is
distance, which buller has ied (possibly innity).
In total we'll learn to proceed queries of arbitrary type in time ( log2 ). But at rst let try
to understand how to approach this problem. Problem is complicated. Queries of dierent types in
arbitrary order, walls may intersect... Let's try to simplify the task. Let there are some walls, but
no new walls will appear. Moreover let all the walls are straight innite lines.
Now the task is following: we have straight lines, which cut out convex polygon, containing
point (0, 0), we need to proceed queries kind of by given ray from (0, 0) nd intersection point of the
ray and the border of the polygon. Solution to the task: let intersect all semiplanes in ( log ),
we'll get an convex polygon. Then each query can made by binary search in (log ) time. Describe
the solution more precisely. Let start from binary search. Take angle of any polygon's vertex and
denote it by . For each other vertex take angle from [, + 2), write down this numbers in
ascending order, we'll get an array of angles, denote it . To know, where the bullet ying into
(, ) will stop, let calculate its angle [, + 2) and nd (using binary search) such minimal
: [] < [ + 1]. Finally we simply intersect the segment, formed by points , + 1 with the
ray (trace of the bullet). Time is (log ). Now let talk about semiplanes intersection. At rst, let
add semiplanes , , , for some big . Now we are sure, intersection
is nite convex polygon. Sort all lines by its angle (angle is from 0 to 2 ). If several lines have the
same angle, let leave only one among them  the nearest to (0, 0). Then we'll add lines in such order
into the stack. Before addition of new line, some top lines in stack may be popped out. Let two top
lines on the stack are 1 and 2 . The top line should be popped out, if point = (1 , 2 ) lies
in opposite side from new line than (0, 0). In the stack we obtain the answer, the polygon. To obtain
whole polygon, let add all the lines twice in the same order. Now contents of the stack is head + the
answer + tail. To cut o the tails consider points of intersection of adjacent lines on the stack and
take any point, which meets twice. Between these two positions the answer lies. The time to build
the structure is () + ().
Complicate the problem: let some new walls (lines) appear. We may use approach of "delayed

). If number of delayed operation

operations" and proceed
each
query
of
type
"bullet"
in
time
(

becomes greater than , wecall the function rebuild, which works

in (), because old walls (lines)

items
we
may
add
in
time
(

log
+ ). In total time to proceed
are already sorted,
and
new

queries is ( ).
We may do it in other way. Let store vertices of the polygon in balanced search tree (before
we stored it in sorted array). To add new line with direction vector and normal (direction of
normal is out of (0, 0)), we need nd the vertex of the polygon such that scalar product , is
maximal possible. It can be done by binary search by sorted array or, if we have BST (and we have),
by descent throw BST tree from root to leaves If the point lies at the same side from the new
line, as point (0, 0) does, we should do nothing. Else we have to erase point and, possibly, some
other adjacent points. Finally we have to add two new points instead of all deleted data. Let delete
vertices in loop, until ordinary point is at the same side from the line as point (0, 0) does. Finally
we add intersection of the line and the segment (process of deletion stops, it gives us two points 
the last deleted, the rst not deleted). So the time to add new line is (log + log ), where 
number of already deleted points. Each point will be deleted only once, so in total we can proceed
queries in ( log ). In terms of speed this solution is much better than previous one. In terms
4/5

of simplicity of implementation the last one is much shorter and simply.

Complicate the problem one more time: now we have not lines, but segments. At st solve
the task in oine (all queries are known in advance). Then we know set of all possible angles of all
ends of all segments. Sort it and build on the obtained array segment tree. Each vertex corresponds
to a certain range of angles. When we add new wall, the new wall is splitted into (log ) parts by
our segment tree. In each of these vertices the wall lies exactly from left border two right border,
means behaves like a line. In total: in each vertex of the segment tree we'll maintain semiplanes
intersection. Note, to build semiplanes intersection inside one vertex of the segment tree, we need
to build a polyline, not a polygon. This polyline passes from left ray to right one (we may assume,
dierence of angles is not greater than 4 ). So procedure of building of semiplanes intersect can be
much simplied in this case  it's enough to add each line only once. Also we do not need to give o
the cycle. So. We have the segment tree. In each vertex of the segment tree semiplanes intersection
lies. Query of type "bullet": angle of the bullet lies in log ranges (vertices of the segment tree). In
each of these vertices we'll ask inner structure in time (log ). Summary time is (log2 ). Query
of time "add new wall": split the wall into log vertices of the segment tree. Add the "line" into
each of the vertices. Summary working time is (log2 ). Amount of used memory is ( log ).
Now to obtain online solution, we make from our segment tree "dynamic segment tree" Initially
segment tree consist of the only vertex  its root. Then during the query to segment tree, which is
proceeding downwards, if we go into nonexistent vertex, we just create it. The process of downning
stops, when length of the segment is less than .
We may also use "delayed operations" here. Then time to proceed query would be ( + log2 ).
Where  number of delayed operations. The structure can be built in time ( log ): sort all the
walls one time,
linear time. Optimal
then in each vertex of the segment tree intersect semiplanes in 3/2
is equal to log . In total summary time to proceed queries is ( log ) .

5/5