Cranker's blog

By Cranker, 10 years ago, In English

Hi I am currently trying to solve my first problem with segment tree. Link to the problem:http://www.hackerearth.com/tracks/pledge-2015-medium/xor-in-tree-1/

I couldn't understand the segment tree implementation in context to this problem which is present in the editorial in the problem setter's solution.

What does T[i] store here?

For the second query, why

int res = path_xor[u] ^ path_xor[v] ^ ST.get_xor(pos[u]) ^ ST.get_xor(pos[v]) ^ a[c];

and not

int res = ST.get_xor(pos[u]) ^ ST.get_xor(pos[v]) ^ a[c]; for the second query?

Currently, I could only understand that the tree is first ordered so that it becomes inline ie topological sort.Now the segment tree works on this topologically sorted tree.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
10 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Read about heavy path decomposition and then return to this problem.