Binary_Index_Tree

#include <iostream>
#include <vector>
using namespace std;

const int MAXINDEX = 100005;
int tree[MAXINDEX]; // BIT array

// Point update for BIT (add val to index idx)
void update(int idx, int val) {
    while (idx < MAXINDEX) {
        tree[idx] += val;
        idx += (idx & -idx);
    }
}

// Range update: add val to range [l, r]
void range_update(int l, int r, int val) {
    update(l, val);       // Add val at start
    update(r + 1, -val);  // Remove val after end
}

// Point query: get value at index idx
int point_query(int idx) {
    int res = 0;
    while (idx > 0) {
        res += tree[idx];
        idx -= (idx & -idx);
    }
    return res;
}

// Example usage
int main() {
    // Range updates
    range_update(2, 5, 10);  // add 10 to all elements in [2, 5]
    range_update(4, 7, 5);   // add 5 to all elements in [4, 7]

    // Point queries
    cout << "Value at index 3: " << point_query(3) << endl;  // should print 10
    cout << "Value at index 5: " << point_query(5) << endl;  // should print 15
    cout << "Value at index 7: " << point_query(7) << endl;  // should print 5
    cout << "Value at index 1: " << point_query(1) << endl;  // should print 0

    return 0;
}