Блог пользователя codeworrior

segment tree
Автор codeworrior, 14 лет назад, По-английски
is it possible to make segment tree to answer dynamic queries ????
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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;
}
}
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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;
}
}
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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...
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    You can erase old segment in log(n) and insert new in log(n). 
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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.
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        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.
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          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?
          → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes, this problem is solved by segment tree.

    Cartesian Tree is not necessary here.

    → Ответить