Structure In a segtree, the basic structure (an array in almost all cases) on which you want to answer queries are stored at leaves of the tree, in the sequential order. All internal nodes is formed by "merging" its left and right children. The overall tree is a complete binary tree of height n. A segtree on 2n elements. The children of node labelled i are (2*i) and (2*i+1). The diagram shows how the binary tree is built up and how the nodes are indexed. Given a node with label i, its left and right children are 2i and 2i+1 respectively,
Read full article from Let us code: Segment Trees
No comments:
Post a Comment