Segment Tree

help
,
1 
#include <iostream>

#define mp(l, r) (l+r)/2
#define lc(i) i*2+1
#define rc(i) i*2+2
using namespace std;
const int N = 1e5 + 5;
int tree[N], arr[N];

void build(int l, int r, int i) {
    if (l == r) tree[i] = arr[l];
    else {
        int mid = mp(l, r);
        build(l, mid, lc(i));
        build(mid + 1, r, rc(i));
        tree[i] = tree[lc(i)] + tree[rc(i)];
    }
}

void update(int l, int r, int i, int idx, int val) {
    if (l == r) {
        arr[idx] += val;
        tree[i] += val;
    } else {
        int mid = mp(l, r);
        if (l <= idx && idx <= mid) update(l, r, lc(i), idx, val);
        else update(l, r, rc(i), idx, val);
        tree[i] = tree[lc(i)] + tree[rc(i)];
    }
}

int query(int l, int r, int start, int end, int i) {
    if (start > r || end < l) return 0;
    if (start <= l && r <= end) return tree[i];
    int mid = mp(l, r);
    int a1 = query(l, mid, start, end, lc(i));
    int a2 = query(mid + 1, r, start, end, rc(i));
    return (a1 + a2);
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    build(0, n - 1, 1);
    cout << query(2, 4, 0, n - 1, 1);
}

I’m trying to implement a segment tree, can’t see why its not working

2

your start and end, you have written them wrong inside the query function. You are changing the l and r of the query interval whereas you should do that with segment interval

3

Following good practices in codes, makes it easy for person debugging to understand codes. As you haven’t provided testcases, I tried to fix it. See if it helps.

#include <iostream>

#define mp(l, r) (l+r)/2
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#define lc(i) i*2
#define rc(i) i*2+1
// <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
using namespace std;
const int N = 1e5 + 5;
int tree[N], arr[N];

void build(int l, int r, int i) {
    if (l == r) tree[i] = arr[l];
    else {
        int mid = mp(l, r);
        build(l, mid, lc(i));
        build(mid + 1, r, rc(i));
        tree[i] = tree[lc(i)] + tree[rc(i)];
    }
}

void update(int l, int r, int i, int idx, int val) {
    if (l == r) {
        arr[idx] += val;
        tree[i] += val;
    } else {
        int mid = mp(l, r);
        if (l <= idx && idx <= mid) update(l, r, lc(i), idx, val);
        else update(l, r, rc(i), idx, val);
        tree[i] = tree[lc(i)] + tree[rc(i)];
    }
}

// =======Its better to use more obvious naming convention atleast for function parameters==================
// like {start: query_left, end: query_right, l: segment_left, r: segment_right, mid: segment_mid}, similar for a1, a2, idx, i etc
int query(int l, int r, int start, int end, int i) {
    if (start > r || end < l) return 0;
    if (start <= l && r <= end) return tree[i];
    int mid = mp(l, r);
    int a1 = query(l, mid, start, end, lc(i));
    int a2 = query(mid + 1, r, start, end, rc(i));
    return (a1 + a2);
}

int main() {
    int n;
    cin >> n;
    // Node 1 of your segment tree stores info about your arr[0] to arr[n-1]
    // that is what build method says (or atleast is expected to say)
    // now left child of node 1, should be 2,3 and not 3,4 
    // so lc(i) = i*2, and rc(i) = i*2+1

    // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    for (int i = 1; i <= n; i++) arr[i-1] = i;//cin >> arr[i];
    build(0, n - 1, 1);
    cout << query(0, n-1, 0, n - 1, 1) << '\n';
    // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
}
1 Like