0

I am trying to implement a simple recurrent function which conceptually similar to segment tree: each node represents a range [l, r] and if current node's index is i, its left and right child will have an index of 2i and 2i+1 respectively. I implement a simple function to print the leaf nodes index (i.e. the segment range represented by the node is [k, k]) and its corresponding range as below:

#include <bits/stdc++.h>
using namespace std;

void recur(int l, int r, int idx){
    if(l > r) return;

    if(l == r) {
        cout << idx << ": " << l << " " << r << endl;
    }
    else {
        int mi = (l + r) >> 1;
        recur(l, mi, idx << 1);
        recur(mi+l, r, (idx << 1) + 1);
    }
}


int main() {
    recur(1, 10, 1);
    return 0;
}

I expect there will be 10 lines of outputs in the format of [idx]: i i where i ranges from 1 to 10. However the output is like below:

16: 1 1
17: 2 2
9: 3 3
10: 4 4
24: 6 6

I tried to debug for hours but have no luck, I wonder what would be the problem or is there any simpler way to implement the recurrence function as described?

1 Answer 1

0

You have a typo on this line: recur(mi+l, r, (idx << 1) + 1);

Instead of mi+l it should be mi+1.

1
  • Oh my god silly me, thanks so much!
    – shole
    Commented Aug 9, 2022 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.