NeFut Logo NeFut
中 Admin Login

In-depth Analysis of Binary Indexed Tree: Core Logic and Efficient Algorithms

Published at: 2026-05-27 09:17 Last updated: 2026-06-11 10:05
#algorithm #Data Structure #C++

Core Logic and Mathematical Principles

The core logic of the Binary Indexed Tree (BIT, also known as Fenwick Tree) lies in utilizing the binary decomposition of positive integers to dynamically maintain prefix sums. It can achieve "point updates" and "range queries" in $O(\log N)$ time complexity, fundamentally breaking the constant impasse of ordinary arrays where updates take $O(1)$ and queries take $O(N)$, or prefix sum arrays where updates take $O(N)$ and queries take $O(1)$.

1. Mathematical Mechanism of $\text{lowbit}$

Define the function $\text{lowbit}(x)$ as the value represented by the "lowest $1$ bit and the following $0$s" in the binary representation of a non-negative integer $x$. By utilizing the two's complement mechanism at the computer's lower level, performing a bitwise AND operation between the source of the positive number $x$ and the complement of its opposite number $-x$ can instantly extract this characteristic bit. The mathematical identity is:

$$\text{lowbit}(x) = x \ \& \ (-x)$$

Proof: Let the lowest $1$ bit of $x$ be at position $k$. Then $x$ can be expressed as $\dots 10\dots0$ (with $k$ trailing $0$s). The two's complement of $-x$ is obtained by inverting $x$ and adding $1$. After inversion, it becomes $\dots 01\dots1$, and adding $1$ changes the $k$-th bit and its lower bits due to carry to $10\dots0$, while the higher bits are completely opposite to $x$. After performing the & operation, all higher bits are cleared, leaving only the $k$-th bit as $1$.

2. Tree Structure Topology

The storage array tree[x] of the Binary Indexed Tree does not record single point values, but is responsible for maintaining the sum of a continuous interval of length $\text{lowbit}(x)$ in the original array A[]. The boundaries of its closed interval are:

$$\text{tree}[x] = \sum_{i = x - \text{lowbit}(x) + 1}^{x} A[i]$$

Based on this topological geometric relationship, two essential topological chains emerge:

State Design and Algorithm Derivation

The state of the Binary Indexed Tree requires only a static space tree[] of the same size as the original array, with valid indices starting from $1$.

1. Point Update (Add) Algorithm Derivation

When the original array element $A[x]$ increases by $\Delta$, all ancestor nodes of tree that govern $A[x]$ must synchronously add $\Delta$ based on the tree structure.

2. Prefix Query (Query) Algorithm Derivation

To solve the prefix sum $S_x = \sum_{i=1}^x A[i]$, utilizing binary decomposition allows the large interval $[1, x]$ to be discretely split into several independent sub-intervals maintained directly by the tree array.

$$\text{Sum}(L, R) = \text{Query}(R) - \text{Query}(L - 1)$$

C++ Standard Source Code

#include <iostream>
#include <vector>
#include <algorithm>

const int MAXN = 500005;

struct BinaryIndexedTree {
    long long tree[MAXN]; // 修改为 long long
    int n;

    // Explicit initialization
    void init(int _n) {
        this->n = _n;
        // Key specification: In multiple data tests, be sure to explicitly clear the entire valid space
        std::fill(tree, tree + n + 1, 0);
    }

    // Inline lowbit operation to suppress function call overhead
    inline int lowbit(int x) const {
        return x & (-x);
    }

    // Point update: add val at position x
    void add(int x, long long val) { // 修改为 long long
        // Critical pitfall: The index of the Binary Indexed Tree strictly starts from 1; passing x = 0 will cause an infinite loop at x + lowbit(0) = 0
        for (; x <= n; x += lowbit(x)) {
            tree[x] += val;
        }
    }

    // Query prefix sum: calculate the sum of the interval [1, x]
    long long query(int x) const { // 修改为 long long
        long long sum = 0; // 修改为 long long
        // Exit condition is x > 0; when x = 0, the increment or decrement chain terminates
        for (; x > 0; x -= lowbit(x)) {
            sum += tree[x];
        }
        return sum;
    }

    // Range query: calculate the standard sum of the interval [l, r]
    long long query_range(int l, int r) const { // 修改为 long long
        if (l > r) return 0;
        // Critical pitfall: When using inclusion-exclusion to calculate the interval, the left endpoint must be l - 1, and note that when l=1, query(0) correctly returns 0
        return query(r) - query(l - 1);
    }
};

int main() {
    // Force unbind I/O to maximize read/write performance
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    if (std::cin >> n >> m) {
        BinaryIndexedTree bit;
        bit.init(n);

        for (int i = 1; i <= n; ++i) {
            long long val; // 修改为 long long
            std::cin >> val;
            bit.add(i, val); // Initial tree construction, single $O(\log N)$, total construction $O(N \log N)$
        }

        for (int i = 0; i < m; ++i) {
            int type, x, y;
            std::cin >> type >> x >> y;
            if (type == 1) {
                bit.add(x, y); // Point update
            } else if (type == 2) {
                std::cout << bit.query_range(x, y) << "\n"; // Range query
            }
        }
    }

    return 0;
}

NOIP 实战避坑指南

  1. 传入下标 0 导致死循环击穿系统栈 树状数组的全部算术逻辑建立在下标 $\ge 1$ 的正整数集合上。如果在代码中错误地触发了 add(0, val) 或 query(0)：由于 $\text{lowbit}(0) = 0 \ \& \ (-0) = 0$，执行 x += lowbit(x) 相当于 0 += 0。for 循环的状态永远无法发生实质性跃迁，程序在评测机上会卡死并触发 Time Limit Exceeded。铁律：凡是涉及离散化坐标或计数模型，必须整体右移一位，保证树状数组输入端点 $\ge 1$。
  2. 数据未做 long long 转化导致区间求和符号位溢出 在诸如“区间动态频次统计”或大数值区间和问题中，原数组单点值虽然在 int 范围内，但经过数十万次 add 操作后，前缀和 tree[x] 的真实值会轻松击穿 $2^{31}-1$。若执着于使用 int tree[]，在执行 query(r) - query(l-1) 时会发生算术整型溢出，数值直接变为负数，输出诡异的错误结果。警惕：只要有频繁累加或区间求和要求，tree 数组与 query 函数返回值一律锁死 `long long`。

经典 NOIP/洛谷 真题

1. 洛谷 P3374 【模板】树状数组 1

2. 洛谷 P3368 【模板】树状数组 2

[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS