### sslotin's blog

By sslotin, 2 years ago,

There is a couple of things about sparse tables that a lot of people I think are doing slightly wrong (including the popular reference implementation by e-maxx).

First, you don't need to precalculate and store logarithms in an array. In fact, whichever procedure compiler will pick to calculate the logarithm is probably going to be much faster than looking it up somewhere in random access memory. The optimal way would be to use __builtin_clz ("count leading zeroes") which uses a separate instruction available on most modern x86's. This way you need just 2 memory reads instead of 3, so on large arrays this should be ~1.5x faster.

Second, memory layout and the order you iterate it matters when you're building the sparse table. There is a total of $2 \times 2 = 4$ ways to do it, and only one of them results in beautiful linear passes that work 1.5-2x faster.

It's easier to implement too:

int a[maxn], mn[logn][maxn];

int rmq(int l, int r) { // [l; r)
int t = __lg(r - l);
return min(mn[t][l], mn[t][r - (1 << t)]);
}

// somewhere in main:
memcpy(mn[0], a, sizeof a);
for (int l = 0; l < logn - 1; l++)
for (int i = 0; i + (2 << l) <= n; i++)
mn[l+1][i] = min(mn[l][i], mn[l][i + (1 << l)]);


Implementation was updated (tnx jef and plainstop):

original query implementation

Also, it's interesting that the last loop is not getting auto-vectorized by the compiler (because std::min is probably something overly complex), and replacing it with simple (x < y ? x : y) gets total speed up to ~3x if you include avx2, but I personally wouldn't do this because it looks cumbersome:

int x = mn[l][i];
int y = mn[l][i + (1 << l)];
mn[l+1][i] = (x < y ? x : y);


(Testing performed on my laptop; didn't run it on CF or other online judges.)

• +112

 » 2 years ago, # |   -30 Sparse tables aren't usually something you need to constant-optimise, especially building them. Also, they contain a lot of redundant information, at least in this version. It's enough to build mn[l][i] if $2^l | i$ and these arrays can also be compressed to take up just $O(N)$ space, which should optimise cache access at high levels.The main advantage of sparse tables is ease of use.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +8 Yeah, agreed; the primary point was that it's both faster and simpler (or at least not harder) to code.I've never heard of this compression thing, but isn't it equivalent to some form of a segment tree? Don't you still need $O(\log n)$ lookups per query?
•  » » » 2 years ago, # ^ |   0 Yeah, O(log) per query and it's pretty much a segment tree without upťdates. It's just that you talked about optimising build time,so I'm pointing out how it can be optimised better (although query performance may suffer) a bit.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +21 How would you keep the $O(1)$ query performance with $O(N)$ memory? I think what you are describing is a segment tree of some sort, instead of a sparse table. Edit: Oops, it seems to have been mentioned before already.
•  » » » 2 years ago, # ^ |   -52 The OP emphasised building performance, which isn't usually viewed as important.$O(1)$ query performance though? How would you do that without $O(N^2)$ preprocessing?
•  » » » » 2 years ago, # ^ |   +47 It sounds like you're missing the point of sparse table. (Or I'm missing the point of your comments or the OP.)The query code in the OP takes $O(1)$ time — it takes the min of precomputed values for two overlapping ranges. That requires all $O(n log n)$ precomputed values. What you described is interval tree rather than sparse table.
•  » » » » » 2 years ago, # ^ |   -29 Huh. I didn't realise queries in sparse table could be done in this way — nice trick. The OP also mentioned $O(\log)$ query, seems like he took it for granted too. Of course, it only works for RMQ and similar idempotent operations, and I don't think I'll ever need it in sparse table, but nice trick.
•  » » » » » » 2 years ago, # ^ |   +35 I have never used sparse table in any other scenario. This is really weird.
•  » » » » » » » 2 years ago, # ^ |   -36 You always needed $O(1)$ rather than $O(\log)$ per query when you used sparse table?
•  » » » » » » » » 2 years ago, # ^ |   +11 What's the advantage of using a Sparse Table then?
•  » » » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   -28 >_>It's right at the end of my first post here.
•  » » » » » » » » » 2 years ago, # ^ |   0 Interesting. I always found them nastier than segment tree because of ton of +-1s.Could you share you implementation?
 » 2 years ago, # |   +37 GCC also offers std::__lg, which does the same thing as your lg function.
•  » » 2 years ago, # ^ |   +5 And the time complexity if $O(1)$ also ?
•  » » » 2 years ago, # ^ |   0 Internally, it seems that the implementation uses __builtin_clz as well.
 » 2 years ago, # |   +16 Your array indices are reversed in your query function.
•  » » 2 years ago, # ^ |   0 they are still reversed in the original query implementation?
•  » » » 2 years ago, # ^ |   0 Yes, t should be the first index.
 » 2 years ago, # |   +5 Can I ask a quite stupid question ? What is the complexity of __builtin_clz ? Is it $O(1)$ or $O(log n)$ ?Thanks <3.
•  » » 2 years ago, # ^ |   0 This might be helpful for you
•  » » 2 years ago, # ^ | ← Rev. 4 →   +10 $O(1)$: it calls a single processor instruction, as most (all?) of __builtin* functions.According to this table, its latency is 3 cycles, the same as multiplying two integers. The instruction is called BSF on Intel Core i7 ("Nehalem").
•  » » » 2 years ago, # ^ |   +5 Thanks