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