Core Functinos

1. Point Update Operation

void update(int idx, int delta) {
  while (idx <= arrSize) {
    tree[idx] += delta;
    idx += idx & -idx; // Propagate to parent nodes
  }
}

2. Prefix Sum Query

long long query(int pos) {
  long long result = 0;
  while (pos > 0) {
    result += tree[pos];
    pos -= pos & -pos; // Move to previous range
  }
  return result;
}

3. Tree Initialization

#include <bits/stdc++.h>

const int MAXN = 1000005;
int arrSize, queryCount;
long long source[MAXN], tree[MAXN];

void update(int idx, int delta) {
  while (idx <= arrSize) {
    tree[idx] += delta;
    idx += idx & -idx;
  }
}

int main() {
  std::cin >> arrSize >> queryCount;
  
  for (int i = 1; i <= arrSize; ++i) {
    std::cin >> source[i];
    update(i, source[i]);
  }
  
  return 0;
}

Application Example 1: Point Updates with Range Queries

This classic scenario involves incrementing single elements and retrieving sums over intervals.

#include <bits/stdc++.h>
#define int long long

const int MAXN = 1000005;
int arrSize, operationCount;
long long original[MAXN], fenwick[MAXN];

void increment(int pos, int value) {
  while (pos <= arrSize) {
    fenwick[pos] += value;
    pos += pos & -pos;
  }
}

int rangeSum(int idx) {
  int total = 0;
  while (idx > 0) {
    total += fenwick[idx];
    idx -= idx & -idx;
  }
  return total;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin >> arrSize >> operationCount;
  
  for (int i = 1; i <= arrSize; ++i) {
    std::cin >> original[i];
    increment(i, original[i]);
  }
  
  while (operationCount--) {
    int type, left, right, value;
    std::cin >> type >> left;
    
    if (type == 1) {
      std::cin >> right >> value;
      increment(left, value);
    } else {
      std::cin >> right;
      std::cout << rangeSum(right) - rangeSum(left - 1) << '\n';
    }
  }
}

Application Example 2: Range Updates with Point Queries

When facing range modifications but single-element retrieval, transform the problem using a difference array approach. The BIT stores differential values rather than direct elements.

#include <bits/stdc++.h>
#define int long long

const int MAXN = 1000005;
int length, operations;
long long values[MAXN], bit[MAXN];

void addDifference(int idx, int delta) {
  while (idx <= length) {
    bit[idx] += delta;
    idx += idx & -idx;
  }
}

int retrievePoint(int idx) {
  int sum = 0;
  while (idx > 0) {
    sum += bit[idx];
    idx -= idx & -idx;
  }
  return sum;
}

signed main() {
  std::cin >> length >> operations;
  
  for (int i = 1; i <= length; ++i) {
    std::cin >> values[i];
    addDifference(i, values[i] - values[i - 1]);
  }
  
  while (operations--) {
    int command, start, end, delta;
    std::cin >> command >> start;
    
    if (command == 1) {
      std::cin >> end >> delta;
      addDifference(start, delta);
      addDifference(end + 1, -delta);
    } else {
      std::cout << retrievePoint(start) << '\n';
    }
  }
}