Perhaps today and/or tomorrow due to a power outage there may be disruptions in the work of Codeforces and Polygon. Please do not plan any important events during this time. If there are details or the exact time, we will definitely publish them. Estimated time of maintenance: from 2 Aug, 16:00 (UTC) to 2 Aug, 20:00 (UTC). ×

ldn060904's blog

By ldn060904, history, 6 weeks ago, In English

So this question came to my mind as I was coding the LCA algorithm using sparse table.

Consider this code

int LCA(int u, int v)
{
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = LOG; i >= 0; i--)
    {
        if (depth[u] - (1 << i) >= depth[v])
        {
            u = P[u][i];
        }
    }
    if (u == v) return u;
    for (int i = LOG; i >= 0; i--)
    {
        if (P[u][i] != P[v][i])
        {
            u = P[u][i];
            v = P[v][i];
        }
    }
    return P[u][0];
}

and this one


int po2[LOG + 1]; void Init() { po2[0] = 1; for (int i = 1; i <= LOG; i++) po2[i] = po2[i - 1] * 2; } int LCA(int u, int v) { if (depth[u] < depth[v]) swap(u, v); for (int i = LOG; i >= 0; i--) { if (depth[u] - po2[i] >= depth[v]) { u = P[u][i]; } } if (u == v) return u; for (int i = LOG; i >= 0; i--) { if (P[u][i] != P[v][i]) { u = P[u][i]; v = P[v][i]; } } return P[u][0]; }

The only difference is that I used 1 << i in the first code and an initialized array in the second one to find the value of $$$2^i$$$. I wonder which one will have better performance.

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ldn060904 (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

The difference should be minimal and you should code the one that is easier for you. If I had to guess, I would say that binary shifting is faster, but it's really something you would have to test on large test cases. Focus on more important time saves :)

»
6 weeks ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

$$$\mathcal{O}(1)$$$ code that doesn't use memory almost always works faster than code that does use memory.