amirjr's blog

By amirjr, history, 45 hours ago, In English

First of all, I'd like to thank greateric, 160cm, and AlirezaBest for their helpful guidance and suggestions. I really appreciate their help!

I've decided to put together a collection of 50 carefully selected Segment Tree problems from Codeforces and share it with the community.

The goal is to make it easier for everyone to find good problems to practice with, without having to spend hours searching for suitable exercises.

I've tried to include a variety of problems, starting with relatively simple ones and gradually moving towards more challenging topics.

I believe these 50 problems provide great practice and can help you build a strong understanding of Segment Trees. If you're learning this data structure or looking to improve your skills, I highly recommend giving them a try!

segment sheet

One last thing: I have to admit that I was quite surprised and a little discouraged by the sudden downvotes on some of my previous blogs. However, that won't stop me from trying to contribute to this community. I genuinely enjoy sharing what I learn and creating things that might help others. As long as there's a chance that my efforts can help even one person, I'll keep trying!

I hope you find this collection useful.

Happy coding, and good luck!

Full text and comments »

  • Vote: I like it
  • +74
  • Vote: I do not like it

By amirjr, history, 4 days ago, In English

There's something I've been wanting to talk about for a while.

Why do we downvote so much?

If you don't like a blog, don't find it interesting, or simply don't feel like reading it, that's totally fine! You can just scroll past it. Nobody expects you to read or agree with everything.

But why downvote instead of simply moving on?

Sometimes there's someone behind that little blog who spent time and effort writing it, someone who's genuinely excited to share their thoughts with others. And sometimes, even one positive vote can make their day and encourage them to keep sharing.

I'm not saying we should upvote everything or that criticism and disagreement are bad. They're actually important. But I think we could all be a little more thoughtful about when and why we give someone a downvote.

What if, instead of discouraging someone, we helped them feel appreciated and motivated to keep contributing?

I genuinely believe that if we start this little cycle of positivity, everyone benefits. More people will feel comfortable sharing their ideas, the community will become friendlier, and we'll all have a better experience.

So, let's try to be a reason someone gets excited to post again, rather than a reason they hesitate next time.

Sometimes, a single upvote costs us absolutely nothing, but it can mean a lot to someone else. :)

Full text and comments »

  • Vote: I like it
  • -16
  • Vote: I do not like it

By amirjr, history, 5 days ago, In English

These three data structures may look quite different, but they can all solve the same range query problems.

Let's compare their ideas using a simple problem.

1. The Problem

Given an array, find the k-th smallest element in a subarray [l, r].

For example:

a = [5, 1, 4, 2, 3]

For l = 2, r = 5, k = 2, the subarray is:

[1, 4, 2, 3]

After sorting, the answer is 2.

We can solve this by answering a simpler query:

count(l, r, x)

The number of elements in [l, r] that are less than or equal to x.

The k-th smallest element is the smallest x satisfying:

count(l, r, x) >= k

2. Merge Sort Tree

A Merge Sort Tree divides the array by positions.

Each node stores a sorted vector of its corresponding segment.

For example, consider an array of length 8:

[5, 1, 4, 2, 3, 7, 6, 8]

Each node stores the sorted elements of its interval.

To answer count(l, r, x), decompose the query into O(log n) nodes and use upper_bound in each vector.

Complexities:

  • Build: O(n log n)
  • Count: O(log² n)
  • K-th smallest: O(log σ × log² n)

Idea: Divide by positions and keep values sorted.

3. Persistent Segment Tree

Instead of dividing by positions, we build a frequency segment tree over the value domain.

root[i] represents the frequency distribution of the first i elements.

We create each version by inserting the next element, copying only the nodes on the update path.

The key observation is:

root[r] - root[l-1]

represents the frequency distribution of the requested subarray.

To find the k-th smallest, calculate the frequency in the left child of both roots. Depending on that count, move left or right.

Complexities:

  • Build: O(n log σ)
  • Query: O(log σ)
  • Memory: O(n log σ) nodes

Idea: Subtract two prefix versions to obtain a range's frequency distribution.

4. Wavelet Tree

A Wavelet Tree also divides by values, but uses bitvectors instead of persistent segment tree nodes.

At each level, elements are partitioned into two groups according to their values.

For our example:

[5, 1, 4, 2, 3]

The root bitvector is:

01011

Here, 1 means left and 0 means right.

We use rank to count how many elements go to each child and map the query interval into that child.

For K-th smallest queries, we simply follow the child containing the k-th element.

Complexities:

  • Build: O(n log σ)
  • Query: O(log σ)
  • Memory: O(n log σ) words with a straightforward implementation.

Idea: Divide by values and use rank operations to navigate the sequence.

5. Comparison

Property Merge Sort Tree Persistent ST Wavelet Tree
Division Position Value Value
Technique Sorted vectors Prefix versions Rank
Count O(log² n) O(log σ) O(log σ)
K-th smallest O(log σ log² n) O(log σ) O(log σ)

There is no universal winner. The best choice depends on the required operations, memory limits, and implementation complexity.

6. Application: 840D — Destiny

Given a query (l, r, k), find the smallest value that occurs more than (r-l+1)/k times.

An important constraint is:

2 <= k <= 5

Let's look at three approaches.

Persistent Segment Tree

Use two prefix versions and traverse the value domain.

If a node's frequency is smaller than the required frequency, discard it. Otherwise, explore its children, visiting the left child first.

At each level, at most k-1 nodes can remain, giving:

O(k log n) per query.

Wavelet Tree

Apply the same pruning idea, but use rank to calculate the frequencies in each child.

The query complexity is also:

O(k log n).

Divide and Conquer

This is the approach used in the official editorial.

Divide the array by positions and precompute the k most frequent values for intervals touching each midpoint.

For a query crossing the midpoint, check the candidates from both halves.

A value occurring more than length/k times must appear among these candidates.

Using occurrence lists and binary search, we can verify them efficiently.

  • Preprocessing: O(kn log n)
  • Query: O(k log n)

The interesting observation: A small constraint such as k <= 5 can completely change the way we approach a problem.

Official Editorial

7. Final Thoughts

We saw three ways to organize the same information:

  • Merge Sort Tree: Divide by positions.
  • Persistent Segment Tree: Subtract prefix histories.
  • Wavelet Tree: Divide by values using rank.

Sometimes, the most interesting part of solving a problem isn't the query itself, but finding the right way to represent the data.

Not gonna lie, I'm just trying to gain some followers. Have mercy and spare me the downvotes! :D

Happy coding!

Full text and comments »

  • Vote: I like it
  • -4
  • Vote: I do not like it