I have a sequence of k nodes
Nk each of which gets hit in succession (with possible skipping).
Every time I visit one of these nodes I need to += the time it took to get there from the previous node. The tricky part is that if I come back to
N1 without reaching
Nk, then these += updates should be dropped.
One method is to keep in each node two quantities: x and y. As we hop nodes we += values into y. If we get to
N1 we reset y to 0. whereas if we reach
Nk we do
x += y for each node.
The problem is that every time we hit
Nk it requires an O(n) operation--even if it might not be the common case for a sequence to return to
N1 without hitting
Nk. Is there a smarter way to do this more efficiently without an O(n) "commit" on every iteration reaching the end?
Consider this example with 3 nodes:
The left shows the subsequence of nodes hit on an iteration and the right shows what the accumulation counters should contain:
(N_1, 2)(N_2, 3)(N_3, 7) ---> (N_1, 2)(N_2, 3)(N_3, 7) (N_1, 4)(N_3, 2) ---> (N_1, 6)(N_2, 3)(N_3, 9) (N_1, 6)(N_2, 3) ---> (N_1, 4)(N_2, 3)(N_3, 2) //nothing changes as this was an "invalid" op because we never hit the end node etc...