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

How to use segment trees on rooted trees?
Автор WalidMasri, история, 8 лет назад, По-английски

Hello CodeForces!

I have the following problem : Given a rooted tree, i have 2 types of queries: 1 q : Mark the Node q colored/uncolored. (Initially they are all uncolored). 2 p : Get the sum of the colored nodes in the p-subtree.

How can i solve this problem using segmentTrees? I couldn't figure out the part where i need to transform my rooted tree into an array, how to do that as well?

Thanks!

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can easily do this by running a modified dfs:

void dfs(int node) {
    used[node]=true;
    pos[node]=++sz;
    from[node]=sz;
    to[node]=sz;
    int i;
    for(i=0;i<(int)(v[node].size());i++) {
        if(!used[v[node][i]]) dfs(v[node][i]),to[node]=max(to[node],to[v[node][i]]);
    }
}

Now pos[X] will be the index of X in the array and [ from[X];to[X] ] will be the subtree of X :)

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

My first dfs-order problem was this one. It has a really great editorial explaining how sub-tree can be converted into subarray using dfs, for update and query using segment/fenwick tree. You can easily understand and solve your problem after reading the editorial.

→ Ответить
  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

    Can you please explain how they are doing the flipping i.e Adding +val in row x , adding -val in row x+1 and so on... I read the editorial and saw solutions of few but could not understand. Some codes are using two segment/fenwick trees. The orignal tree is flattened by dfs.

    In one code I saw... https://mirror.codeforces.com/contest/383/submission/37359401 . In update step, They are adding val at the start[node] and subtracting val at end[node]+1... I dont understand why this works and gives the alternate thing.

    In one other solution... https://mirror.codeforces.com/contest/383/submission/37689950 . In one of the trees (odd seg) , in the update step , val is added , in the other tree (even seg) , val is substracted. I dont understand how these two trees are used to arrive at the alternate addition and subtraction.

    Thanks in advance!

    → Ответить
    • »
      »
      »
      10 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      they are maintaining two bit-arrays, one for odd parity (for odd level nodes) and one for even parity.

      Now for query of type 1 you simply add val at tin and sub val at tout+1 (range update in bit) in the bit-array corresponding to the node's parity

      For query of type 2, you query array's value in both parity arrays if node's parity is 1 then all the values in parity 0 array that were added to the node must be subtracted (because in parity 0 array if we add any value to a node of parity 1 it needs to be subtracted) that's how final answer is simply a[x] + query(tin[x], par)-query(tin[x], Par)

      where par = parity[x]

      → Ответить
»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

You can write pre-order traversal of the tree's nodes and note that subtrees now correspond to subsegments of that order. Now you have range sum query problem.

→ Ответить