Hi everyone!

Today we will talk about something that might be useful in programming competitions. Yay! Also great thanks to antontrygubO_o for sharing this with me and others in a Discord server.

Let's implement a data structure that maintains a big number $$$N$$$ in base $$$b$$$ and supports the following:

• Assuming $$$c$$$ is a small global constant, given integers $$$|x|, |y| \leq n$$$, add $$$x b^y$$$ to $$$N$$$.
• Given $$$k$$$ and assuming $$$N \geq 0$$$, print the $$$k$$$-th digit of $$$N$$$.
• Check if $$$N$$$ is positive, negative or equals to $$$0$$$.

Each operation should take at most $$$O(\log n)$$$ amortized time. While some approach you may think of immediately would imply using segment tree, or a similar structure, the solution proposed here only requires std::map, so it's much shorter and easier to implement (at the slight expense of increased constant factor). It may be used in the following problems:

• #2302. 「NOI2017」整数
• 1817E - Полусумма
• 1810F - M-дерево

If you implement the big integers in these numbers the standard way (i.e. keeping digits in the $$$[0, b)$$$ segment, carefully executing carries, etc), you will quickly learn that you may get in trouble because you may be forced to do and undo a lot of carry operations which chain up and so you need to frequently change large segments between the values of $$$0$$$ and $$$b-1$$$.

Now, stop being fooled by the non-negative propaganda! You don't have to do it! Let's give ourselves some slack and allow negative digits. Well, just a bit of them. Instead of maintaining digits in $$$[0,b)$$$, let's now maintain them in the interval $$$(-b, b)$$$. It seems like a tiny change, but the effect is tremendous. On one hand, the representation of any number is not unique anymore. On the other hand, when we actually reach the value $$$b$$$ or $$$-b$$$, we wrap them back to $$$0$$$, and carry $$$1$$$ or $$$-1$$$ to the next digit correspondingly.

Noticed anything? The carry now wraps us from the endpoints of the interval to its middle instead of from one endpoint to another! It would be easy to add $$$1$$$ to a particular bit, turn it into $$$b$$$ and cause a chain of carries by it. But! If after that we add $$$-1$$$ to the same bit, it will not wrap all the bits back to $$$b-1$$$! It will just change this specific bit to $$$-1$$$! So, we give up the uniqueness of the representation, but we gain a whole lot of stability in exchange.

The C++ implementation for the first two queries is also quite concise:

struct nega_num {
    const int base = 1 << 30;

    map<int, int> digs;

    void add(int a, int b) {
        digs[b] += a;
        int t;
        do {
            t = digs[b] / base;
            digs[b + 1] += t;
            digs[b] -= t * base;
            if(digs[b] == 0) {
                digs.erase(b);
            }
            b++;
        } while(t);
        if(digs[b] == 0) {
            digs.erase(b);
        }
    }

    int get(int k) {
        auto it = digs.lower_bound(k);
        int ans = it == end(digs) || it->first > k ? 0 : it->second;
        if(it != begin(digs) && prev(it)->second < 0) {
            ans--;
        }
        return (ans + base) % base;
    }
} me;

I tested it on #2302. 「NOI2017」整数 and it works!

P.S. Applying it to 1817E - Полусумма and 1810F - M-дерево is left to the curious reader as an exercise :)

P.P.S. Is this trick well-known? Does it have a name?