Recomputing every span after each insert would throw away the skip list's speed. Today you maintain spans incrementally during insert, using a rank array that records how far the descent had traveled at each level.
Update spans inside insert so a freshly built list has correct spans with no rebuild.
The trick to updating spans without recomputing is to track, during the descent, how
far you have already traveled. Keep a rank array beside update: rank[i] is the
number of level-0 steps covered by the time the descent dropped onto level i. Since
rank[0] is the new node’s level-0 position and rank[i] is where the level-i
predecessor sits, the difference rank[0] - rank[i] tells you how many level-0 steps
lie between that predecessor and the new node.
With that number, splicing sets two spans at each level of the new tower. The new
pointer inherits what its predecessor used to cover, minus the part now on the
predecessor’s side: newNode.span[i] = update[i].span[i] - (rank[0] - rank[i]). And
the predecessor’s pointer, now landing on the new node, gets (rank[0] - rank[i]) + 1. Levels above the new tower gain one skipped node, so their span just
increments. It is fiddly the first time, but it is the same accounting every indexed
skip list (including Redis) uses, and it keeps insert at expected O(log n) with spans
always exact. A duplicate update still changes nothing, spans included.
// Alongside update[], keep rank[i] = how many level-0 steps the descent// had covered when it dropped to level i. Then when splicing the new node:// newNode.span[i] = update[i].span[i] - (rank[0] - rank[i])// update[i].span[i] = (rank[0] - rank[i]) + 1// For levels above the new node's height, the pointer now skips one more:// update[i].span[i]++// When raising the list level, the head's new pointers start with span = length.