Блог пользователя Thunder8971

Автор Thunder8971, 4 недели назад, По-английски

Hello, Codeforces!

It's been a while since I last seriously participated in competitive programming. I've thought about coming back many times, but today I want to share something a little different from an algorithm or a contest experience.

I've always loved competing. Not just winning, but facing difficult problems, challenging myself, and discovering how far I could go. Whether it was competitive programming, research, or simply learning something new, I loved pursuing things that seemed almost impossible.

But sometimes life changes in ways we could never anticipate.

In 2025, I was diagnosed with retinitis pigmentosa, a progressive retinal disease. My night vision and peripheral vision were already severely compromised, and I was told I might have around five years of useful sight left.

I was terrified. Suddenly, everything seemed pointless. I knew I could still learn and accomplish things without sight, but I couldn't imagine losing the life I knew. It felt as though everything I dreamed of had been overshadowed by something I couldn't stop.

The strange thing was that my academic and professional performance didn't decline. I continued studying, working, and fulfilling my responsibilities just as I always had. But the things I used to do simply because I loved them were different. Competitive programming, playing piano or violin, and even sharing what I knew with others no longer brought me the happiness they once had. Little by little, I stopped doing many of those things.

From the outside, very little seemed to have changed. Inside, I felt almost nothing. When someone reminded me of my past achievements, I knew they were talking about me, yet those memories felt as though they belonged to someone else. I couldn't connect the person I remembered with the person living my life. Sometimes I cried; other times I felt completely empty, even when I wasn't alone.

I didn't want to become someone different. I just wanted to feel like myself again.

My family stood by me throughout that time, even when I couldn't explain what I was feeling. I also received encouragement from people I'll always be grateful for. I tried returning to things that once made me happy, and at one point, almost instinctively, I helped someone who needed to study. But even then, I couldn't feel the connection I was searching for.

Then, during the first week of May 2026, something unexpected happened.

I was alone in my room when I noticed a blue hardcover book on my shelf. I picked it up and realized it was something I had written when I was fifteen, filled with my dreams, experiences, and thoughts about pursuing what matters to us. I'd written it hoping to inspire others to follow their dreams with everything they had.

I never imagined that, years later, I would be the one who needed those words.

As I read, I remembered not only what I wanted to accomplish, but why. For the first time in what felt like an eternity, I felt connected to myself again. I was happy because I could finally recognize myself, and sad because I couldn't believe how long I'd spent feeling like a stranger in my own life.

The book I'd written to inspire others ended up inspiring me.

A few days later, something happened that I still find almost unbelievable. Someone I thought I would never hear from again suddenly contacted me. She had once been one of my closest friends, but we'd lost contact two years earlier, and I hadn't known what had happened to her.

We had shared competitions, research, dreams, and ideals. When we started talking again, she reminded me of experiences we'd had together, including moments I'd completely forgotten. Hearing those stories brought back memories that had felt lost to me for so long.

She also wanted to help me return to the things I used to love. She even had ideas for activities we could enjoy together, just as we had shared so many interests before. We talked about the life we'd once dreamed of, filled with learning, curiosity, competitions, and seemingly impossible goals. Despite the difficulties she'd experienced, she still believed in those dreams.

To her, she was simply being herself, reconnecting with an old friend. To me, those conversations and her willingness to share those experiences again meant more than she could imagine.

Little by little, I returned to swimming, piano, violin, and astronomy. I took out my old telescope and, for the first time, saw Saturn's rings. I can't describe how wonderful that felt. My family, friends, that book, and my own efforts had all played a part. I wasn't trying to return to the past. I simply wanted to feel like myself again and enjoy the life I was still living.

Recently, I visited my retinal specialist again. He explained that my disease was already advanced and had an unusual presentation: despite my severely compromised visual field and night vision, the characteristic retinal pigmentation wasn't clearly visible. I couldn't help finding a little irony in having retinitis pigmentosa without visible pigment.

But his message was serious. He told me that I could lose my remaining vision soon, although no one could predict exactly when. He encouraged me to enjoy the vision I still have and reminded me that, ultimately, only God had the final say.

Those words were difficult to hear. I'd be lying if I said I wasn't afraid. But this time, something was different. I don't want that fear to take away the life I still have. There are so many things I want to learn, discover, create, and share with others. I don't know what the future will bring, but I know I want to keep moving forward, searching for solutions and pursuing my dreams, even when the path becomes difficult.

I may not be able to choose what happens to my vision, but I don't want to lose myself to that uncertainty again. I want to keep doing what I love, appreciating the people around me, and finding reasons to smile along the way.

Later, while practicing violin and thinking about everything I'd been through, I felt something I hadn't felt in a long time: nostalgia and pride. Pride in being able to enjoy the things I love again, and in finally feeling like myself.

So why share this story here? Because behind every Codeforces handle, there's a person with a life we cannot fully see. Someone might stop competing or disappear for months. Someone else might keep performing well while quietly struggling. We can't know what someone is going through just by looking at their rating or achievements.

Maybe someone reading this has been feeling lost, has stopped enjoying something they once loved, or is going through something so difficult that they can't imagine things getting better. If that's you, I want you to know that you're not alone.

I know that hearing someone tell you to be strong doesn't magically make things better. There were times when I couldn't even recognize myself, much less imagine feeling happy again. But things can change, sometimes in ways we never expect. It might take time, support, or something that reminds you of what matters to you. You don't have to figure everything out today, and asking for help doesn't mean you've given up.

Somewhere in this community, there's someone who once felt completely lost too, and who eventually found his way back. If you ever feel like talking, you're welcome to send me a message. I may not have all the answers, but I'd be happy to listen when I can.

As for me, I still intend to compete, study, do research, and search for ways to contribute to a solution for my disease. Some attempts may fail, and I may need help or a different approach, but I have no intention of giving up on that search.

And I still carry the dream I wrote about at fifteen: helping build a world where more people have the chance to pursue their own dreams.

If you have a story or a few words of encouragement you'd like to share, feel free to leave them in the comments. Perhaps someone else reading this might need to hear them, too.

Thank you for reading my story. From the bottom of my heart, I hope that whatever you're facing, you find the support, hope, and opportunities to keep pursuing what matters to you. Even when the road ahead seems uncertain, there may still be beautiful things waiting to be discovered.

See you in the next contest. ❤️⚡

Полный текст и комментарии »

  • Проголосовать: нравится
  • +232
  • Проголосовать: не нравится

Автор Thunder8971, 18 месяцев назад, По-английски

Hello, Codeforces!

Back in 2023, I spent almost an entire week trying to understand how to implement an iterative segment tree with lazy propagation. I had seen implementations before, but some parts felt almost like magic. I could understand what the code was doing, yet I couldn't always explain why it worked or how I would have discovered those operations myself.

Eventually, I decided to approach the problem from scratch, reasoning about the tree, its nodes, and the information each operation needed. That experience led me to write my original tutorial on iterative segment trees.

Looking back, there was something I hadn't fully explored: many of the operations I was performing could be simplified by understanding which parts of the tree actually need to change.

In this blog, I want to revisit that idea. Rather than presenting another template to memorize, I'd like to show how we can derive an iterative lazy segment tree from a few properties, and then use those same properties to solve something beyond ordinary range queries.

We'll use two familiar operations:

  1. Add a value $$$v$$$ to every element in a range.
  2. Find the minimum value in a range.

Both will take $$$O(\log N)$$$ time. Later, we'll extend the same structure to find the first position satisfying a condition, also in $$$O(\log N)$$$.

What does a node actually store?

Let's start with an array $$$A$$$ of length $$$N$$$.

As usual, we round its capacity up to the smallest power of two greater than or equal to $$$N$$$. Let's call this capacity $$$n$$$. The original elements occupy the leaves starting at index $$$n$$$, while each internal node $$$p$$$ has children $$$2p$$$ and $$$2p+1$$$.

We will use zero-based indexing and half-open intervals $$$[l,r)$$$ throughout the implementation. This makes the boundary operations easier to express.

If we only needed range minimum queries, each internal node would satisfy:

$$$ st[p]=\min(st[2p],st[2p+1]). $$$

That part is straightforward. The interesting question appears when we add lazy propagation.

Suppose we add $$$v$$$ to every element represented by some node $$$p$$$. We don't want to visit all its descendants, so we store the update at $$$p$$$ and postpone applying it to its children.

But what should $$$st[p]$$$ represent while that update is pending?

For range addition and minimum queries, we have a useful property:

$$$ \min(a_1+v,\ldots,a_k+v) = \min(a_1,\ldots,a_k)+v. $$$

So we can immediately update the minimum stored at $$$p$$$, while remembering that its children still need to receive $$$v$$$.

This gives us the invariant:

$$$ \boxed{st[p]=\min(st[2p],st[2p+1])+lazy[p]} $$$

for every internal node.

Here, $$$lazy[p]$$$ represents an addition already reflected in $$$st[p]$$$, but not yet propagated to its children. A node's stored minimum may still exclude pending updates from its strict ancestors, so those updates must be pushed before we inspect it independently.

This distinction is important. It means a pending update doesn't make the node's own aggregate incorrect. Its aggregate is already updated; only the information in its descendants is waiting.

From that invariant, three operations follow naturally:

  • apply(p, v) updates the aggregate at $$$p$$$ and records the pending update.
  • push(p) transfers that pending update to both children.
  • pull(p) reconstructs the aggregate at $$$p$$$ from its children while respecting its own pending update.

Notice that pull must include lazy[p]. If we simply replaced $$$st[p]$$$ with the minimum of its children, we could accidentally discard an update that had been applied to the parent but not yet propagated.

Once these rules are clear, lazy propagation becomes less about remembering a sequence of instructions and more about preserving a relationship between the nodes.

Why do only two paths matter?

Now comes my favorite observation.

Suppose we want to process an interval $$$[l,r)$$$. An ordinary iterative segment tree decomposes this interval into a small collection of disjoint nodes, each representing a segment completely contained in our query.

For example, with eight elements, the interval $$$[2,7)$$$ can be represented by:

$$$ [2,4),\quad [4,6),\quad [6,7). $$$

We don't need to visit every element individually. We only need those three nodes.

A straightforward lazy implementation might propagate pending updates from the root to each selected node separately. That works as an initial idea, but there are $$$O(\log N)$$$ selected nodes, and each propagation can cost $$$O(\log N)$$$.

We end up with $$$O(\log^2 N)$$$ work.

But look at what happens if we consider the boundaries of the interval.

Every selected node is completely contained in $$$[l,r)$$$. Furthermore, because the decomposition uses maximal complete segments, its parent cannot be completely contained in the interval.

In other words, every strict ancestor of a selected node that matters for propagation must partially overlap the requested interval.

And here is the key property:

If a node's segment partially overlaps a contiguous interval, that segment must contain at least one of the interval's two boundary elements.

Therefore, all ancestors that we need to prepare are contained in the union of two root-to-leaf paths: the paths to $$$l$$$ and $$$r-1$$$.

Instead of propagating updates separately for every selected node, we can propagate along those two paths first.

After that, the usual iterative interval decomposition can safely read the aggregates of its selected nodes.

The same idea works when updating a range.

We propagate along the two boundary paths, apply the update to the selected nodes, and then reconstruct the necessary ancestors along those same paths.

The important detail is that nodes completely covered by the update can keep their lazy tags. We don't need to rebuild their entire subtrees, and our pull invariant ensures that reconstructing an ancestor doesn't erase those pending updates.

Both paths have length $$$O(\log N)$$$, and the interval decomposition contains $$$O(\log N)$$$ nodes. Therefore:

$$$ T(N)=O(\log N)+O(\log N)+O(\log N) =\boxed{O(\log N)}. $$$

What I like about this observation is that we don't need a special trick for every node. We only need to understand which ancestors may contain information that affects the interval.

Putting everything together

Now let's implement everything.

We'll use st for the minimum values and lazy for pending additions. The functions pushPath and pullPath do exactly what we discussed: propagate information toward a boundary and reconstruct aggregates on the way back.

All ranges use $$$[l,r)$$$, and queries assume $$$0 \le l \lt r \le N$$$.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = (1LL << 60);

struct SegTree {
    int n, h;
    vector<ll> st, lazy;

    SegTree(vector<ll> a) {
        int m = a.size();
        n = 1;
        h = 0;

        while (n < m) {
            n *= 2;
            h++;
        }

        st.assign(2 * n, INF);
        lazy.assign(n, 0);

        for (int i = 0; i < m; i++)
            st[n + i] = a[i];

        for (int i = n - 1; i > 0; i--)
            pull(i);
    }

    void pull(int p) {
        st[p] = min(st[2 * p], st[2 * p + 1])
                + lazy[p];
    }

    void apply(int p, ll v) {
        st[p] += v;
        if (p < n) lazy[p] += v;
    }

    void push(int p) {
        if (lazy[p] == 0) return;

        apply(2 * p, lazy[p]);
        apply(2 * p + 1, lazy[p]);
        lazy[p] = 0;
    }

    void pushPath(int p) {
        for (int s = h; s > 0; s--)
            push(p >> s);
    }

    void pullPath(int p) {
        for (p /= 2; p > 0; p /= 2)
            pull(p);
    }

    // Add v to [l, r).
    void add(int l, int r, ll v) {
        if (l == r) return;

        int L = l + n;
        int R = r + n - 1;

        pushPath(L);
        pushPath(R);

        for (l += n, r += n; l < r;
             l /= 2, r /= 2) {

            if (l & 1) apply(l++, v);
            if (r & 1) apply(--r, v);
        }

        pullPath(L);
        pullPath(R);
    }

    // Minimum of [l, r).
    ll query(int l, int r) {
        pushPath(l + n);
        pushPath(r + n - 1);

        ll ans = INF;

        for (l += n, r += n; l < r;
             l /= 2, r /= 2) {

            if (l & 1) ans = min(ans, st[l++]);
            if (r & 1) ans = min(ans, st[--r]);
        }

        return ans;
    }

    // Find the leftmost valid leaf inside a node.
    int descend(int p, ll x) {
        while (p < n) {
            push(p);
            p *= 2;

            if (st[p] >= x)
                p++;
        }

        return p - n;
    }

    // First i in [l, r) with A[i] < x.
    // Returns -1 if there is no such position.
    int firstBelow(int l, int r, ll x) {
        if (l == r) return -1;

        pushPath(l + n);
        pushPath(r + n - 1);

        vector<int> right;

        for (l += n, r += n; l < r;
             l /= 2, r /= 2) {

            if (l & 1) {
                if (st[l] < x)
                    return descend(l, x);
                l++;
            }

            if (r & 1)
                right.push_back(--r);
        }

        for (int i = (int)right.size() - 1;
             i >= 0; i--) {

            int p = right[i];

            if (st[p] < x)
                return descend(p, x);
        }

        return -1;
    }
};

The implementation has three main ideas worth remembering.

First, apply updates the minimum immediately, so we can answer queries using a node even when its children haven't received the pending addition.

Second, pushPath and pullPath work only along the two boundary paths. We never need to propagate every node selected by the interval decomposition.

Third, pull preserves the invariant by including lazy[p]. This is why rebuilding a node doesn't destroy an update that has not reached its children.

Let's try a small example:

int main() {
    vector<ll> a = {7, 3, 8, 5, 9};

    SegTree st(a);

    st.add(1, 4, 4);
    // a = {7, 7, 12, 9, 9}

    cout << st.query(0, 5) << '\n';
    // 7

    cout << st.firstBelow(2, 5, 10) << '\n';
    // 3
}

The padded leaves contain INF, the neutral value for minimum queries. As long as we operate within the original array and the values remain safely within the range of long long, they won't affect our answers.

We can do more than calculate a minimum

Now suppose we need to answer a slightly different question:

Given $$$l$$$, $$$r$$$, and $$$x$$$, find the smallest index $$$i$$$ such that

$$$ l \le i \lt r \quad\text{and}\quad A_i \lt x. $$$

One possible approach is to binary search over the answer and repeatedly query the minimum of a prefix. That would cost $$$O(\log^2 N)$$$.

But we already know how to decompose an interval into $$$O(\log N)$$$ nodes. Why not use that decomposition directly?

Recall that each node stores the minimum of its segment.

If a node has

$$$ st[p] \ge x, $$$

then none of the elements in that segment can satisfy our condition. We can skip the entire segment.

Otherwise, the segment contains at least one valid answer.

So we can process the selected nodes from left to right until we find the first one whose minimum is below $$$x$$$. Once we find it, we descend through that node, always trying the left child first.

If the left child's minimum is below $$$x$$$, the answer must be somewhere inside it. Otherwise, we move to the right child.

Eventually, we reach the first valid leaf.

This also explains the right vector in firstBelow. During the iterative decomposition, we discover the left-side nodes in left-to-right order, but the right-side nodes in the opposite order. We save those right-side nodes and process them in reverse so that we always search from left to right.

The number of selected nodes is $$$O(\log N)$$$, and we perform at most one additional descent of length $$$O(\log N)$$$. Therefore, the entire search is still:

$$$ \boxed{O(\log N)}. $$$

There is an important detail here: our query is not binary searching because the individual elements are sorted. They don't need to be sorted at all.

We are using the minimum stored in each node to eliminate entire segments that cannot contain an answer.

This is the idea behind guided segment-tree searches, including operations such as max_right and min_left in AtCoder Library.

I think this is a particularly useful way to look at segment trees. They don't just answer questions about an interval; they can also help us locate where a condition first becomes true or false, provided our stored information lets us safely reject entire segments.

For example, imagine tracking the remaining capacity of a resource across different time slots. A reservation decreases the capacity of an interval, while a cancellation increases it.

With the same structure, we can update capacities, obtain the minimum remaining capacity, or find the first time slot whose capacity falls below a chosen threshold.

Of course, this kind of search is possible with recursive segment trees too. The advantage here is that we can derive it naturally from the same iterative decomposition we already understand.

What I would remember instead of the code

There are many implementations of iterative segment trees, and I'm certainly not claiming this technique is new. In particular, I recommend reading Al.Cash's Efficient and easy segment trees and the AtCoder Lazy Segment Tree documentation, which cover these ideas and their generalizations.

What I wanted to contribute was a way of connecting the operations to the properties that make them work.

If I had to reconstruct this implementation during a contest, I would start with three questions:

  1. What does each node represent? Define the aggregate and the invariant that must hold when updates are pending.
  2. Which nodes can affect my answer? For an interval, understand its canonical decomposition and the two boundary paths.
  3. Can my aggregate eliminate an entire segment? If so, perhaps I can turn a range query into a guided search.

I also think it's worth remembering that this implementation is specifically designed for range addition and range minimum. Other combinations of updates and queries may require different stored information, different lazy tags, or different rules for composing updates. The general idea transfers, but the formulas should always be derived rather than copied blindly.

Back in 2023, I spent a week trying to understand something that already had several existing explanations. Looking back, I don't think that time was wasted. It taught me that understanding why a structure works can be just as valuable as learning how to implement it.

I hope this explanation helps someone who has looked at an iterative lazy segment tree and wondered where all those operations came from.

Thank you for reading! If you notice a mistake, have a different way of explaining these properties, or know an interesting application, I'd be happy to discuss it in the comments.

Happy coding!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

Автор Thunder8971, история, 22 месяца назад, По-английски

After today's contest, jiangly reached a rating of 3977, just 23 points below 4000. Could jiangly be the next to reach a rating of 4000?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +73
  • Проголосовать: не нравится