I'm having trouble understand a part of a paper, page 7 the last 3 paragraphs. In the part I'm struggling with the author suggests how to solve a problem which I describe below.It's not necessary to understand anything else in the paper to tackle the problem. The Problem: Say I have a graph, and a given vertex $v$. There's a set of vertices of size k, call it $N$, of other vertices s.t $d(v,N[1])\leq d(v,N[2]) \leq...\leq d(v,N[k])$. Given a subsequence $(i,i+1,...,i')$ of $(1,2,3,...,k)$ I need to identify index $j$ for which $d(v,N[j+1]) - d(v,N[j])$ is largest. I need to be able to find those $j$ indexes in $O(log k)$ time at most.In the paper, we work only with even indexes. ($I=(2,4,...)$ instead of $(1,2,...$). Otherwise it's the same as described above. My questions are the following: Third paragraph from the end1) When he builds the binary tree $T$, why does identifying the end points canonical subsequences takes $O(k)$? Doesn't it takes $O(log k)$? 2) When he said that a bottom-up $O(k)$ can algorithm can identify for each canonical subsequence the index $j$, doesn't it take $O(log k)$? (starting at the leaves associated with the edges of the subsequence)Second paragraph from the end3) I've did a toy example, but the algorithm, doesn't seem to work. This is what I've tried:(The tree is constructing in the way the author suggests in the third paragraph from the end, the notation i,j means a sequence (i,i+1,....,j-1,j)) I guess I'm missing something, but I just can't figure out what.
Problem understaind a data structure based on binary tree in a paper
data structures;binary trees