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

Printing Segtree for debugging purposes
Автор vrooooom, история, 4 года назад, По-английски

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

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

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

You can print as u recurse in the SegTree query?

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

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.

→ Ответить
»
16 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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";
}
→ Ответить