What are competitive programming problems that require a tree data structure to solve them? I want to practice my problem-solving skills that involve the usage of a tree data structure (e.g. Binary Search Tree, Heap, Fenwick Tree, etc.)

The problem should make me search for the right tree data structure and apply it in solving the problem, but not manipulate the tree itself. Hence, problems like the lowest common ancestor, inorder traversal, etc. do not count.

One nice problem that I know is as follows:

N pixels in a row are originally coloured as white:
WWWWWWWWWWWWWWW // N=15 in this case

We now keep recolouring all pixels between position i and position j 
with a different colour c for T times:

T = 1: WWWBBBBBWWWWWWW // i = 4, j = 8, c = B
T = 2: WWWBBGGGGWWWWWW // i = 6, j = 9, c = G
T = 3: YYYBBGGGGWWWWWW // i = 1, j = 3, c = Y
T = 4: YBBBBBGGGWWWWWW // i = 2, j = 5, c = B
...

At the end, you are asked to print the colour of each pixel.


Since N and T can be large, one requires a tree data structure to efficiently update the colour pattern of the pixels. 

Can anyone suggest good programming problems of this nature?
How about Huffman encodings?


  Given a text that uses an alphabet of $n$ unique characters, how can we uniquely encode the alphabet so that the text uses the smallest amount of bits?


More formally for Huffman encodings (as formulated by Tardos &amp; Kleinberg in their book Algorithm Design):


  Given an alphabet and a set of frequencies for letters, we would like to produce a prefix code that is as efficient as possible - namely, a prefix code that minimises the average number of bits per letters $ABL(\gamma) = \sum\limits_{x\in S} f_x|\gamma(x)|$. We will call such a prefix code optimal.


This has an $O(n \log n)$ solution.