samedi 25 avril 2015

Bug in C++ Segment Tree Implementation?


I implemented a segment tree that seemed to work when I tested it with small inputs, but produces wrong answer when I tried to solve a problem with it. I'm sure that the bug is in the segment tree, but I can't find it. Can someone find the bug in my implementation? Code is below.

class SegmentTree
{
public:
    int* st;
    int* a;
    int length;
    SegmentTree(int* arr, int n)
    {
        length = n;
        a = arr;
        int height = (int)(ceil(log2(n)));
        int maxSize = 2 * (1 << height) - 1;
        st = new int[maxSize];
        build(0, 0, length - 1);
    }
    int f(int a, int b) // change for different problems
    {
        return max(a, b);
    }
    void build(int node, int l, int r)
    {
    if (l == r)
        st[node] = a[l];
    else
    {
        int mid = (l + r) / 2;
        build(node * 2 + 1, l, mid);
        build(node * 2 + 2, mid + 1, r);
        st[node] = f(st[node * 2 + 1], st[node * 2 + 2]);
    }

    void update(int i, int v)
    {
        update(0, 0, length - 1, i, v); //if sum query last parameter should     be v - a[i], otherwise should be v
        a[i] = v;
    }
    void update(int node, int sl, int sr, int i, int v) 
    {
        if (i < sl || i > sr)
            return;
        st[node] = f(st[node], v);
        if (sl != sr)
        {
            int mid = (sl + sr) / 2;
            update(node * 2 + 1, sl, mid, i, v);
            update(node * 2 + 2, mid + 1, sr, i, v);
        }
    }

    int query(int ql, int qr)
    {
        return query(0, 0, length - 1, ql, qr);
    }
    int query(int node, int sl, int sr, int ql, int qr)
    {
        if (sl > qr || sr < ql)
            return -1;
        if (sl >= ql && sr <= qr)
            return st[node];
        int mid = (sl + sr) / 2;
        int a = query(node * 2 + 1, sl, mid, ql, qr);
        int b = query(node * 2 + 2, mid + 1, sr, ql, qr);
        if (a == -1)
            return b;
        if (b == -1)
            return a;
        return f(a, b);
    }
};

int main()
{
    int a[] = { 4, 1, 2, 0, 6 };
    SegmentTree st(a, 5);
    cout << st.query(0, 2) << endl;
}


Aucun commentaire:

Enregistrer un commentaire