javacoder1's blog

PROBLEM IN UNDERSTANDING PROPAGATING TREE(383C)
By javacoder1, history, 9 years ago, In English

I am having problem understanding how we are utilising Binary Indexed tree to solve the problem.The DFS part is clear as well as the notion of levels. But i am unable to understand how BIT is used. http://mirror.codeforces.com/contest/383/problem/C link.

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

i solved it with segment tree . 1. find starting time and finishing time and also depth of each vertex with a dfs

  1. in segment tree interval of each vertex v with we do operation on it is [str[v] , fin[v]] because all of children of v have a starting time greater than v and finishing time less than v

  2. build 2 segment trees one for the ones with even depth and one for odd depth now when you r updating a vertex v you change intervals of one segment tree by +val and the other -val (just compare their depth mod 2)

  3. now for get queries just go throught every segment with vertex v in it and add it's value to answer !

check my code if u want (it's ugly :) ) http://mirror.codeforces.com/contest/383/submission/13809240

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It would be much better if anyone could explain it with binary indexed tree.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      :| u can use BIT instead of segment trees for the problem (for + val and — val )

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        it's just the problem of adding a number to an interval which can be solved with BIT too .

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Could you elaborate in detail?

          → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It would be helpful if you could explain how binary indexed tree is used either through diagram or something like that sort?

          → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Some nodes b/w [str[v], fin[v]] will have +val, while remaining nodes will have -val . Why are we adding +val on whole range [str(v) , fin[v]] ?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      http://mirror.codeforces.com/contest/383/submission/15232082

      check this solution. Here we are maintaining the notion of levels. Suppose the level is odd we are adding -val to all the children and if the level is even we are adding +val.But we have to make the children of let's say even level nodes -val we are taking care of this when we are taking the query look , we have taken negative sign which makes this +val appear as -val. Suppose now we have performed this query on a node which has a subtree of depth 6 and this node is at even level.all nodes at odd and even level have a value of +val.Another query at it's children which is at odd level make all the children of this child node achieve value of -val1 .The grandchild of node has value of +val-val1 which is what we desire and this node is at even level so we are simply adding this value at the query with the initail value.the child of this grandchild has too the value +val-val1 but we desire -val+val1 which is taken care in query by taking the negative sign in case of odd levels and adding it to the initial value.By this you can notice that the problem is symmetric if during update at odd levels we do +val then during query we also do +val and so for even levels we do -val in update and query. As you can see single BIT is enough but you can also use two BIT's one for updating even levels with +val (bit1) and one for updating odd levels with -val (bit2).on query at odd level we do -(bit1 + bit2) and at even level we do +(bit1+bit2)

      → Reply