codeworrior's blog

segment tree
By codeworrior, 14 years ago, In English
is it possible to make segment tree to answer dynamic queries ????
  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I'm sorry, i forgot to change language.

If range of segment tree too large, then you can balanced search tree, Cartesian tree for example. Also you can generate tree on the fly, i.e. you can create vertex of tree only if you go to this vertex:

struct vert{
vert *l,*r;
vert *to_left() {
if (!l) l=new vert;
return l;
}
}
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
i didnt understood ur approach exactly...can u explain a bit more..
my problem is that i hav to find rmq queries of a segment in log n time and i should be able to change the values of the interval also in log n time...
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can erase old segment in log(n) and insert new in log(n). 
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      In your idea to update a segment we must erase k elements and than insert k element, were k is the length of the segment. So you are wrong.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        You can store one more variable for each vertex of segment tree:

        struct ST {
        int d,i;
        } s[1000000];

        You can push value of i to it's children:

        s[2*i].i=s[2*i+1].i=s[i].i;
        s[i].i=0;

        You can write value of i in d if this vertex is leaf:

        s[i].d+=s[i].i;
        s[i].i=0;

        Now, you can update not only one element, but any segment, if it has vertex. It works for O(log n).

        void update(int v,int l,int r,int x,int y,int v) 
        /*
        v - vertex number
        l,r - borders of vertex
        x,y - border of interval for change
        v - value for addition in all elements in [x,y]
        */
        {
        if (r<x || y<l) return;
        if (l==r) {s[v].d=s[v].i; s[v].i=0; return s[v].d;}
        s[2*v].i=s[2*v+1].i=s[v].i;
        s[v].i=0;
        if (x<=l && r<=y) s[v].i+=v; else {
        update(v*2,l,(l+r)/2,x,y,v);
        update(v*2+1,(l+r)/2+1,r,x,y,v);
        }
        }

        Maybe this code has some bugs.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          By using the update function you provided, what would the query function be like? In other words, how do we integrate that additional variable 'i' into the querying function to determine minimum value?
          → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, this problem is solved by segment tree.

    Cartesian Tree is not necessary here.

    → Reply