algorithmc++14recurrencesegment-tree

Recurrence function to print range of segment

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?

Solution

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

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