1.Segment Tree:
To Read :
http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static
http://ronzii.wordpress.com/2011/07/08/segment-tree-tutorial/
http://se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html
http://olympiad.cs.uct.ac.za/presentations/camp3_2007/interval_trees.pdf
http://codeforces.com/blog/entry/6281
http://apps.topcoder.com/forums/?module=Thread&threadID=651820&start=0&mc=2#1146133
http://www.algorithmist.com/index.php/Segmented_Trees
http://letuskode.blogspot.in/2013/01/segtrees.html
http://wcipeg.com/wiki/Heavy-light_decomposition
http://discuss.codechef.com/questions/5960/rnestescape-from-the-mines
http://ideone.com/dPS5N (Heavy Light implementation).
https://sites.google.com/site/indy256/algo/heavy_light (Heavy Light implementation).
Problems:
http://www.spoj.com/problems/GSS1
http://www.spoj.com/problems/GSS2
http://www.spoj.com/problems/GSS3
http://www.spoj.com/problems/GSS4
http://www.spoj.com/problems/GSS5
http://www.spoj.com/problems/GSS6
http://www.spoj.com/problems/GSS7
http://www.spoj.com/problems/ANDROUND/
http://www.spoj.com/problems/BRCKTS/
http://www.spoj.com/problems/DQUERY/
http://www.spoj.com/problems/FREQUENT/
http://www.spoj.com/problems/HEAPULM/
http://www.spoj.com/problems/HELPR2D2/
http://www.spoj.com/problems/KGSS/
http://www.spoj.com/problems/MKTHNUM/
http://www.spoj.com/problems/NICEDAY/
http://www.spoj.com/problems/YODANESS/
http://www.spoj.pl/problems/INCSEQ/
http://www.spoj.pl/problems/INCDSEQ/
http://www.spoj.pl/problems/KQUERY/
http://www.spoj.pl/problems/QTREE/
http://www.spoj.pl/problems/QTREE2/
http://www.spoj.pl/problems/QTREE3/
http://www.spoj.com/problems/QTREE4/
http://www.spoj.com/problems/QTREE5/
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/
http://www.spoj.com/problems/MULTQ3/
http://www.spoj.com/problems/RPAR/
http://www.spoj.com/problems/PATULJCI/
http://www.spoj.com/problems/DISUBSTR/
http://www.spoj.com/problems/HORRIBLE
http://www.spoj.pl/problems/IOPC1207/
http://www.spoj.com/problems/SEGSQRSS/
http://www.spoj.com/problems/ORDERSET/
http://www.spoj.com/problems/HELPR2D2/
http://www.spoj.com/problems/TEMPLEQ
http://www.codechef.com/problems/QTREE
http://www.codechef.com/problems/LEBOBBLE
http://www.codechef.com/problems/DGCD
http://www.codechef.com/problems/QUERY
http://codeforces.com/problemset/problem/280/D
http://codeforces.com/problemset/problem/117/E
http://codeforces.com/problemset/problem/167/D
http://codeforces.com/problemset/problem/266/E
http://codeforces.com/problemset/problem/145/E
http://codeforces.com/problemset/problem/226/E
http://codeforces.com/problemset/problem/311/C
http://codeforces.com/problemset/problem/276/E
http://codeforces.com/problemset/problem/221/D
http://codeforces.com/problemset/problem/174/C
http://codeforces.com/problemset/problem/301/D
http://codeforces.com/problemset/problem/61/E
http://codeforces.com/problemset/problem/103/D
http://codeforces.com/problemset/problem/165/D
http://codeforces.com/problemset/problem/52/C
http://codeforces.com/problemset/problem/85/D
http://codeforces.com/problemset/problem/242/E
http://codeforces.com/problemset/problem/111/B
http://codeforces.com/problemset/problem/220/B
http://codeforces.com/problemset/problem/195/E
http://codeforces.com/problemset/problem/219/E
http://codeforces.com/problemset/problem/281/D
http://codeforces.com/problemset/problem/121/E
http://codeforces.com/problemset/problem/86/D
http://codeforces.com/problemset/problem/182/C
http://codeforces.com/problemset/problem/19/D
http://codeforces.com/problemset/problem/258/E
http://codeforces.com/problemset/problem/190/E
http://codeforces.com/problemset/problem/295/E
http://codeforces.com/problemset/problem/160/E
http://codeforces.com/problemset/problem/163/E
http://codeforces.com/problemset/problem/192/E
http://codeforces.com/problemset/problem/316/E3
http://codeforces.com/problemset/problem/280/E
http://codeforces.com/problemset/problem/238/D
SRM 310 -> Floating Median
http://acm.pku.edu.cn/JudgeOnline/problem?id=1986
http://acm.pku.edu.cn/JudgeOnline/problem?id=2374
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2045
http://acm.pku.edu.cn/JudgeOnline/problem?id=2763
http://www.spoj.pl/problems/QTREE2/
http://acm.uva.es/p/v109/10938.html
http://acm.sgu.ru/problem.php?contest=0&problem=155
- BIT (also called Fenwick Tree). Mostly problems of BIT can also be solved by Segment Tree. But it is shorted and faster to code. Hence it is sometimes very easy.
To Read:
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
http://p--np.blogspot.in/2011/04/binary-indexed-tree.html
http://www.algorithmist.com/index.php/Fenwick_tree
http://en.wikipedia.org/wiki/Fenwick_tree
http://pavelsimo.blogspot.in/2012/09/counting-inversions-in-array-using-BIT.html
http://petr-mitrichev.blogspot.in/2013/05/fenwick-tree-range-updates.html
Problems:
http://community.topcoder.com/stat?c=problem_statement&pm=10976
And try some earlier problems which are solvable by this data structure to practice more.
Try mobile problem of IOI. 2D BIT.
- Dynamic Programming (DP):
To Read:
http://en.wikipedia.org/wiki/Edit_distance
http://www.codechef.com/wiki/tutorial-dynamic-programming
Problems:
SGU Problems : 269, 273, 304, 317, 356, 396, 445, 447, 458, 489, 494
http://www.spoj.com/problems/SAMER08D/
http://acm.sgu.ru/problem.php?contest=0&problem=199
http://www.spoj.com/problems/MDOLLS/
http://www.spoj.com/problems/MSTICK/
http://www.spoj.com/problems/MCARDS/
http://www.spoj.com/problems/MIXTURES/
http://www.spoj.com/problems/SCUBADIV/
http://z-trening.com/tasks.php?show_task=5000000355
http://z-trening.com/tasks.php?show_task=5000000286
http://z-trening.com/tasks.php?show_task=5000000465
http://z-trening.com/tasks.php?show_task=5000000310
http://z-trening.com/tasks.php?show_task=5000000778
http://z-trening.com/tasks.php?show_task=5000000363
http://z-trening.com/tasks.php?show_task=5000001024
http://www.spoj.com/problems/VOCV/
http://www.spoj.com/problems/PT07F/
http://www.spoj.com/problems/PT07X/
http://z-trening.com/tasks.php?show_task=5000000070
http://z-trening.com/tasks.php?show_task=5000000569
http://z-trening.com/tasks.php?show_task=5000000441
http://z-trening.com/tasks.php?show_task=5000000050
http://www.spoj.com/problems/RENT/
http://www.spoj.com/problems/INCSEQ/
http://www.spoj.com/problems/INCDSEQ/
http://z-trening.com/tasks.php?show_task=5000000624
http://z-trening.com/tasks.php?show_task=5000000742
http://z-trening.com/tasks.php?show_task=5000000749
http://z-trening.com/tasks.php?show_task=5000001044
http://www.spoj.com/problems/SEQ/
http://www.spoj.com/problems/SPP/
http://z-trening.com/tasks.php?show_task=5000000078
http://z-trening.com/tasks.php?show_task=5000000543
http://z-trening.com/tasks.php?show_task=5000000718
http://z-trening.com/tasks.php?show_task=5000000237
http://z-trening.com/tasks.php?show_task=5000000311
http://www.spoj.com/problems/MORSE/ (dp + trie) Very Hard.
http://www.spoj.com/problems/MPOLY/
http://www.spoj.com/problems/CVXPOLY/
http://www.spoj.com/problems/MTRIAREA/
http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=2222
http://www.lightoj.com/login_main.php?url=volume_showproblem.php?problem=1122
http://www.lightoj.com/login_main.php?url=volume_showproblem.php?problem=1122
http://www.lightoj.com/login_main.php?url=volume_showproblem.php?problem=1125
Game (IOI 2008, Practice session)
http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static
Graph Theory:
http://community.topcoder.com/stat?c=problem_statement&pm=10736
http://www.spoj.com/problems/TRAFFICN/
http://www.spoj.com/problems/PA06ANT/
http://www.spoj.com/problems/PT07Z/
http://www.spoj.com/problems/EXPLOSN/
http://www.spoj.com/problems/BUGLIFE/
http://www.spoj.com/problems/SSORT/
http://www.spoj.com/problems/ARBITRAG/
http://www.spoj.com/problems/CODE/
http://www.spoj.com/problems/FROGGER/
http://www.spoj.com/problems/GCPC11C/
http://www.spoj.com/problems/GCPC11J/
http://www.spoj.com/problems/GHOSTS/
http://www.spoj.com/problems/MAKETREE/
http://www.spoj.com/problems/PARADOX/
http://www.spoj.com/problems/QTREE/
http://www.spoj.com/problems/QTREE2/
http://www.spoj.com/problems/QUEEN/
http://www.spoj.com/problems/ROBOTGRI/
http://www.spoj.com/problems/ELEVTRBL/
http://www.spoj.com/problems/TRIPINV/
http://www.spoj.com/problems/CAPCITY/
http://www.spoj.com/problems/KOICOST/
SHARE
Top comments (0)