Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
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;
          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];
              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 | 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 | 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?