树状数组

lowbit(x)

lowbit既能求出该节点及其下面子节点的个数,也能帮助区间下标转换

$lowbit(x) = x & (-x)$

例如lowbit(8):

$8_{10} = 1000_{2}$ 负数符号位不同( $-8_{10} = 1000_2$

计算机以补码计算

8的补码$1000$, -8的补码$-8 = 1000_2 = 0111_2 + 1 = 1000_2$

$1000 & 1000=1000$ 所以$lowbit(8) = 8$

• 将普通数组放入像树一样的数组$c$,$c$存所有子节点的和,如果是叶节点($lowbit(i)=1$)则是$a[i]$的值

OI-WIKI 树状数组图解

单点修改,查询区间和 Luogu

• 这里将普通数列放入树状数组中是一个一个插入的(其他的还不会)
• 数组数组维护的是原数列,那么getsum(x)求的是前缀和[1,x], 求$[x,y]$相减就行了

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 5e5+10;

int a[maxn],c[maxn],n,m;

inline int lowbit(int x) { return x & -x; }

// 插入值
void add(int index,int val) { // index 下标,val值
    while (index <= n) { // 避免越界
        c[index] += val; // 最下一层维护,然后向树上走,维护包含初始c[index]的c[]节点
        index += lowbit(index);
    }
}

int getsum(int index) {
    int ans = 0;
    while (index >= 1) {
        ans += c[index]; // [index-lowbit(index),index]的值都包含在c[index]中
        index -= lowbit(index);
    }
    return ans;
}

int main() {
    cin >> n >> m;
    for (int i=1; i<=n; ++i) {
        int temp; cin >> temp;
        add(i,temp);
    }
    while(m--) {
        int index,x,y;
        cin >> index >> x >> y;
        if (index == 1)
            add(x,y);
        else
            cout << getsum(y) - getsum(x-1) << endl;
    }
    return 0;
}

区间修改,查询区间和 / 单点查询 Lougu

1. 不在维护原数组,转而维护原数组的差分数组，**差分数组的某个前缀和 = 原数组的某个元素值**

原数组$a$,差分数组$b$, $[1,r]$的和为$\sum_{i=1}^{r}a[i]$, 差分数组定义:$a[i] =\sum_{j=1}^{i}b[j]$

$\sum_{i=1}^{r}a[i] = \sum_{i=1}^{r} \sum_{j=1}^{i} b[j]$

$=(b_1)+(b_1+b_2)+(b_1+b_2+b_3)+…+(b_1+b_2+b_3+..+b_r)$

$=b_1r + b_2(r-1) + b_3*(r-2)+…+b_{r-1}2+b_r1$

$=b_1*(r-1+1) + b_2*(r-2+1) + b_3*(r-3+1)+…+b_{r-1}(r-(r-1)+1) + b_r(r-r+1)$

$=\sum_{i=1}^{r}b_i*(r-i+1) = (r+1) \sum_{i=1}^{r} b_i - \sum_{i=1}^{r} b_i*i$

• 开2个树状数组分别维护$b_i$和$b_i*i$

2. 查询区间$[l,r]$的和

设$sum[i]$表示$[1,i]$的和 (前缀和),$[l,r] = sum(r) - sum(l-1)$

$sum(r) = (r+1)\sum_{i=1}^{r} b_i - \sum_{i=1}^{r} i*b_i$

$sum(l-1) = (l-1+1)\sum_{i=1}^{l-1} b_i - \sum_{i=1}^{l-1} i*b_i$

3. 在上面单点修改中,$getsum()$求的是原数组的前缀和,那么这里求出来的就是差分数组的前缀和,就是原数列某元素值,解决单点询问
4. 区间修改利用差分数组的性质,修改区间$[l,r]$即修改$b[l]+=val,b[r+1]-=val$,(单点修改),

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 5e5+10;
ll t1[maxn],t2[maxn];
int n;

inline int lowbit(int x) { return x & (-x); }

void add(int index,int val) {
    ll temp = (ll)(index * val);
    while (index <= n) {
        t1[index] += (ll)val;
        t2[index] += temp;
        index += lowbit(index);
    }
}

ll getval(ll *t,int index) {
    ll ans = 0;
    while (index) {
        ans += t[index];
        index -= lowbit(index);
    }
    return ans;
}

void operate(int l,int r,int val) {
    add(l,val);
    add(r+1,-val);
}

ll getsum(int l,int r) {
    return (r+1)*getval(t1,r) - l*getval(t1,l-1) - (getval(t2,r) - getval(t2,l-1));
}

int m;

int main() {
    cin >> n >> m;
    int last = 0;
    for (int i=1; i<=n; ++i) {
        int temp; cin >> temp;
        add(i,temp-last);
        last = temp;
    }
    while (m--) {
        int index,x,y,k;
        cin >> index;
        if (index == 1) {
            cin >> x >> y >> k;
            operate(x,y,k);
        } else {
            cin >> k;
            //cout << getsum(k,k) << endl;
            cout << getval(t1,k) << endl;
        }
    }
    return 0;
}

---

• 学树状数组顺便重新学补码,前缀和,差分数组,这些性质(cao)

  前缀和 和 差分可以看做是可逆的