JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Segment trees
 Segment trees | Reply I was wondering how to use the segment tree implementation. I adjusted it so that M[] and A[] are global arrays but I must not be using it write. The initialize() function seems to work right but the query() function doesn't. I fill A[] from 0..n-1. I call initialize(1,0,n-1), and for each query I call query(1,0,e-1,i,j). What's the problem?Here's my edit to the code:```void initialize(intnode, int b, int e) { if (b == e) M[node] = b; else { initialize(2 * node, b, (b + e) / 2, M, A, N); initialize(2 * node + 1, (b + e) / 2 + 1, e, M, A, N); if (A[M[2 * node]] <= A[M[2 * node + 1]]) M[node] = M[2 * node]; else M[node] = M[2 * node + 1]; } }   int query(int node, int b, int e,int i, int j) { int p1, p2; if (i > e || j < b) return -1; if (b >= i && e <= j) return M[node]; p1 = query(2 * node, b, (b + e) / 2, M, A, i, j); p2 = query(2 * node + 1, (b + e) / 2 + 1, e, M, A, i, j); //These assignment statements seem to be causing the trouble //if I eliminate then and simply return p1 or p2 I have no problem //but I suspect that the complexity is ruined because of this. if (p1 == -1) return M[node] = p2; if (p2 == -1) return M[node] = p1; if (A[p1] <= A[p2]) return M[node] = p1; return M[node] = p2; } ```
 Re: Segment trees (response to post by mhayter1) | Reply Has anyone tried to use this code before?
 Re: Segment trees (response to post by mhayter1) | Reply Hi, IMHO, there is some error in this implementation : we cannot use an array to store the segment tree. It's not quite true, that "left child of x is 2x , and right child of x is 2x+1" - this is only true , when the number of elements is 2^n. To see this, just try an array of length 6. Hope this help :)
 Re: Segment trees (response to post by hungson175) | Reply I see this has been posted a long time ago, but it may help someone that is interested in this tutorial.There is no problem to store a segment tree in the described way. You just need to be sure when the tree have N leaves, you may need upto 2 * N2 nodes, where N2 is the smallest number that is equal or greater than N, and is also a power of 2.
 Re: Segment trees (response to post by anastasov.bg) | Reply When using segment tree, when you have N nodes, you need an array with length 4*N.
 Re: Segment trees (response to post by anastasov.bg) | Reply In this implementation, query function changes tree in every call. My question is that, do I have to re-initialize the tree in each query, or is there any way not to update the tree while query?
 Re: Segment trees (response to post by ortschun) | Reply my usual segtree implementation doesn't update tree while querying. remove the assignment in "return M[node] = ...;"
 Re: Segment trees (response to post by fushar) | Reply How can we use segment trees dynamically?
 Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Segment trees Previous Thread  |  Next Thread