# What are competitive programming problems that require a tree data structure to solve them?

Computer Science Educators Asked by mercury0114 on August 21, 2021

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?

One nice problem that I found is:

Given n segments in 2D Euclidean space, find two segments that intersect.


Seek for $$O(n cdot log(n))$$ solution.

https://cp-algorithms.com/geometry/intersecting_segments.html

Correct answer by mercury0114 on August 21, 2021

You have a list $$[l_1, l_2, ..., l_N]$$ of $$N$$ distinct integers.

Then you receive $$K$$ queries where the query $$q_i = (a_i, b_i)$$ asks you to find the minimal element in the sublist $$[l_{a_i}, l_{a_i+1}, ..., l_{b_i}]$$

Preprocess the list to serve $$K$$ queries in less than $$O(K cdot N)$$ time.

Answered by mercury0114 on August 21, 2021

Another one is the following job scheduling problem:

N jobs are arriving with priorities:

priority_1  arrival_time_1  execution_time_1
priority_2  arrival_time_2  execution_time_2
...
priority_N  arrival_time_N  execution_time_N

The arriving jobs are queued. When the CPU can process the next job, he will pick
the one that has already arrived and has the highest priority in the queue. The
job will then be processed for a time equal to its execution time.

Determine the maximum time some job will have to wait in the queue until being
processed.


An efficient implementation of the queue will give $$O(N cdot log(N))$$ solution.

Answered by mercury0114 on August 21, 2021

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 & 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) = sumlimits_{xin S} f_x|gamma(x)|$$. We will call such a prefix code optimal.

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

Answered by MrHug on August 21, 2021

## Related Questions

### AP Computer Science A vs. OCP

1  Asked on June 19, 2021 by marwi

### What would be a good project for teaching big program concepts?

4  Asked on June 15, 2021

### Looking for a text book on object-oriented concepts and programming

1  Asked on June 12, 2021

### REPL environment for teacher assignments

1  Asked on June 9, 2021 by jan-koupil

### Any good resource for introducing kids to programming using Python’s Turtle Graphics?

7  Asked on June 1, 2021 by kam-eissawy

### Feedback request: an assignment on programming a research paper

1  Asked on May 21, 2021

### Self Learning Quantum Computing and helpful resources that can aid, guide and teach Quantum Computing from CS&E perspective

1  Asked on May 17, 2021 by rewcie

### Cheating on labs

11  Asked on May 14, 2021

### What is good age to start learning programming?

15  Asked on April 10, 2021

### How to learn Java as a beginner?

2  Asked on April 4, 2021 by long-le-thanh

### Is there a good book for combinatorics for programmers?

1  Asked on March 25, 2021 by boujozo

### Common questions students may ask when they learn OOP?

2  Asked on March 14, 2021

### What “process instruction” should instructors give students when assigning a team project?

4  Asked on March 12, 2021

### I know C++ 2003 How to start learning C++ 2017?

2  Asked on March 11, 2021

### introduction materials to the actor model?

0  Asked on March 9, 2021

### games for teaching html

0  Asked on March 8, 2021

### Difference between a Bachelor’s degree and a Master’s degree in CS

2  Asked on February 24, 2021 by kanayt

### How should I handle over-demanding assignment providers?

3  Asked on February 24, 2021 by a-bakker

### Student not understanding explanation the 1st, 2nd… and 8th time

4  Asked on February 16, 2021 by rares-dima

### Is CS50 AP available for new teachers for 2020-2021?

1  Asked on February 4, 2021 by m-braden

### Ask a Question

Get help from others!