树状数组

Skyzhou666 · 2024-11-28 23:02:50 · 算法·理论

树状数组

一天在知乎上刷到一篇文章 有没有一段代码，让你为人类的智慧击节叫好？，看到里面的树状数组，发现我居然没水过这个数据结构的blog（

可以在空间n，时间O(logn)的情况下实现单点修改，区间查询，而且代码真的极为简洁，可谓之神作。

直接贴上模板先

int n;
int tree[MAXN];

void Tadd(int i, int x)
{
    for(; i <= n; i += i & -i) tree[i] += x;
}

int Tsum(int i)
{
    int re = 0;
    for(; i; i -= i & -i) re += tree[i];
    return re;
}

注意这里的Tsum查询之后是前缀和

查询s_l到s_r的方法：

Tsum(r) - Tsum(l-1)

关于神秘的i & -i,ChatGPT给出了以下答案：

在C++中，i & -i 是一个经典的位运算技巧，它用于获取整数 i 的二进制表示中最低位的1（lowest set bit）。它可以在许多算法中派上用场，尤其是涉及位运算优化或数据结构（如树状数组）的情况下。