I have always found a lack of books on advanced things that I've encountered in competitive programming like Fenwick trees, link-cut trees, rmq etc. Can anybody recommend book(s) that contain these things?
I don't know how many books there are on those topics. A lot of the data structures in higher level competitive programming problems have pretty niche uses. It might be best to look at papers instead. Here's one on the Fenwick/Binary Indexed Tree:
Check out Competitive Programming by the Halim brothers. One of the best books on the subject, explains many algorithms and different problem types you will find in a competitive setting. The book also includes solutions to 100s of UvA problems.
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=503...