Using Fenwick Tree to solve "Gravel" Problem

help
, ,
1

Problem Link: SPREAD Problem - CodeChef

Can anyone please help me out to fix my code for this problem. I believe I’m missing out a small detail but I can’t figure it out.

Code:

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

#define ll long long

ll sum(vector<ll> &fenwick, int i) { 
	ll res = 0;
	while (i > 0) {
        res += fenwick[i];
        i -= (i & (-i));
    }
	return res;
}

void update(vector<ll> &fenwick, int i, ll inc) { 
    int n = fenwick.size() - 1;
    while (i <= n) {
        fenwick[i] += inc;
        i += (i & (-i));
    }
}

void solve() {
    ll n, m, c;
    cin >> n >> m >> c;

    vector<ll> fenwick(n + 1, 0);
    for (int i = 1; i <= n; ++i) { 
        update(fenwick, i, c);
    }
    
    while (m--) {
        ll u, v, k, p;
        char type;
        cin >> type;
        if (type == 'S') {
            cin >> u >> v >> k;
            update(fenwick, u, +k);
            update(fenwick, v + 1, -k);
        }
        else {
            cin >> p;
            cout << sum(fenwick, p) - sum(fenwick, p - 1) << "\n";
        }
    }
}

int main() {
 ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}
1 Like