Problems on (segment trees, range queries, interval trees, k-d trees, Binary index trees)

general
, , , , , ,
1

Hi {guys,girls},

I’ve been participating in long competitions and trying to break the barrier of 7 questions(no success till date :()
I get stuck on problems associated with range queries, trees etc(QTREE*, GERALD2, QPOINT, MONOPLOY, and the list continues)

I want to learn all these trees and put a nail into the coffin once for all and I think If we could share some problems related to these concepts(codechef, spoj, codeforces, topcoder), it would be helpful for all the fellow coders.

TOPICS: Segment trees, lazy propagation, interval trees, splay trees, link-cut trees, Binary index trees, Kd trees, Quad trees, range queries, EVERYTHING \m/

Here are some problems I’ve found.

LEBOBBLE, QTREE, MSTICK, SORTING, SEABAL, PPLUCKY, RRANGE(SPOJ)

http://www.spoj.pl/problems/DQUERY/

http://www.spoj.pl/problems/KQUERY/

http://www.spoj.pl/problems/FREQUENT/

http://www.spoj.pl/problems/GSS1/

http://www.spoj.pl/problems/GSS2/

http://www.spoj.pl/problems/GSS3/

http://www.spoj.pl/problems/GSS5/

http://www.spoj.pl/problems/KGSS/

http://www.spoj.pl/problems/HELPR2D2/

http://www.spoj.pl/problems/INCSEQ/

http://www.spoj.pl/problems/INCDSEQ/

http://www.spoj.pl/problems/QTREE/

http://www.spoj.pl/problems/QTREE2/

http://www.spoj.pl/problems/QTREE3/

http://www.spoj.pl/problems/BRCKTS/

http://www.spoj.pl/problems/CTRICK/

http://www.spoj.pl/problems/MATSUM/

http://www.spoj.pl/problems/RATING/

http://www.spoj.pl/problems/RRSCHED/

http://www.spoj.pl/problems/SUPPER/

http://www.spoj.pl/problems/ORDERS/

Please add to this list. Thanks in advance

26 Likes
2

@nitinj appreciate your initiative !

3

lightoj has two category for segment tree related problems.
Link: http://lightoj.com/volume_problemcategory.php?user_id=3857&category=Segment%20Tree/Interval%20Tree
Link: http://lightoj.com/volume_problemcategory.php?user_id=3857&category=Range%20Minimum%20Query/Lowest%20Common%20Ancestor

4

We can search here: http://a2oj.com/Categories.jsp accoding to tags, categories :slight_smile:
Also, I will be adding to this list if I get something.

5

@nitinj , if it is possible, it would be good if the problems are somewhat sorted according to the level of difficulty. Would really help beginners of this topic to master it :slight_smile:

4 Likes
6

You can find a large collection of segment tree / BIT problems here : http://praveendhinwacoding.blogspot.in/2013/06/700-problems-to-understand-you-complete.html

7

You people can also use this link in order to find the problems of your choice …Be it a Segment tree problem or a dp problem or some other algo or data structure

8

Hey, Check out this link. Nice website with the best UI so far and problems classified according to categories from 20+ OJ!

http://acm.bnu.edu.cn/v3/problem_category.php