vrooooom's blog

Printing Segtree for debugging purposes
By vrooooom, history, 4 years ago, In English

Hey there, :)

Normally whenever I am working on a task requiring a segment tree or some similar data structure problem, and my code does not work, I find myself at a loss for what to do because it seems kind of hard to tell whether or not the segment tree is working properly or not...

I wrote this quick function to print a somewhat simple segment tree, but it feels rather ugly, and I don't think it would be feasible for more complex data structures.

Print_seg function

Do you have any functions/scripts that you use to debug data structure problems, and if so, I would appreciate it if you would share it in the comments :p

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

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

You can print as u recurse in the SegTree query?

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

There is definitely no way that fits all. I’d say, try to actively think what you are looking for while debugging and output that. I know that one thing I do often is print the aggregates over the whole tree (the “implicit array”) at each step. This usually makes it easier to assert the correctness, due to the flat representation. However, it works for some applications and not for others.

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Great idea. You can use setw() to make it more beautiful like this code

void print() {
    int layer = n; // n smallest power of 2 that great than or equal to the size of seg_tree
    for (int i = 0; i < 2*n - 1; i++) {
        cout << setw(layer) << seg_tree[i] << " ";
        if (__builtin_popcount(i + 2) == 1) {
            layer /= 2;
            cout << "\n";
        }

    }
    cout << "\n";
}
→ Reply