题解：P3374 【模板】树状数组 1

· · 题解

P3374 【模板】树状数组 1 题解

题解区已经有很多奆佬了，希望可以夹缝求生。

题意

对一个数列进行两种操作：

**pass**。 **前缀和差分时间复杂度** - 预处理 $O(n)$。 - 操作1 进行处理 $O(n)$。 - 操作2 $O(1)$。 $m$ 次操作时间复杂度最坏 $O(nm)$。 **pass**。 那我们就该引入树状数组了 ## 算法分析 树状数组以二叉树为底层逻辑，二叉树是一种优秀的数据结构，许多以二叉树为底层的算法都可以将复杂度降为 $\log$ 级别，树状数组也是如此。 ![](https://cdn.luogu.com.cn/upload/image_hosting/o86vjxgk.png) 这是一个树状数组示意图，其中 $c$ 数组就表示树状数组。树状数组每一个值都储存着这个位置所管理的前缀和。当我们要更新值的时候，重新处理前缀和只需要一层一层往上更新管理当前位置的值就行了。 此时我们就要引入一个函数```lowbit```。 ### 核心函数 #### lowbit ```lowbit```是指将参数转为二进制后最后一个 $1$ 所代表的位置，而在这里~~虽然不知道原理~~像是一个梯子，

x + lowbit(x)$ 就可以访问往上一层的下标。编码很简单，只有一行

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

我更喜欢取别名：

#define lowbit(x) x & -x;

更新值

理解上一个函数之后就很简单了：

/*可以把整个过程理解为爬梯子
|-------|
|-------|
|-------|   
|tree[x]| x 
x:当前位置 lowbit(x):往上一个台阶的距离 tree[x]:当前位置能管理到所有值的前缀和
*/
void update(int x,int d) //最开始在x 把a[x] 加上d
{
    while(x <= n)       //梯子最高就n层
    {
        tree[x] += d;     //当前位置加上d
        x += lowbit(x);   //往上一层
    }
}

求 [x,y] 前缀和

输出和普通前缀和差不多，用 sum(x) 表示 x 的前缀和，输出 sum(x) - sum(y - 1) 就行了。

int sum(int x)
{
//和刚刚理解方法差不多 这里是下楼梯，顺便把所有的加上
  int ans = 0;      //答案
    while(x > 0)      //最少1层
    {
        ans += tree[x]; //加上值
        x -= lowbit(x); //往下
    }
    return ans;
}

至此所有的都分析完了。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define pc putchar
#define lowbit(x) x & -x 
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 5e5 + 10;
int n,T;
int tree[maxn];
int op,x,y;
void update(int x,int d)
{
    while(x <= n)
    {
        tree[x] += d;
        x += lowbit(x); 
    }
} //更新部分
int sum(int x)
{
    int ans = 0;
    while(x > 0)
    {
        ans += tree[x];
        x -= lowbit(x); 
    }
    return ans;
} //前缀和
void solve()
{
    scanf("%d%d%d",&op,&x,&y);
    if(op == 1) update(x,y);                //操作1:更新
    else printf("%d\n",sum(y) - sum(x - 1));//操作2:前缀和
} //单词操作
int main()
{
    scanf("%d%d",&n,&T);
    for(int i=1;i<=n;i++) scanf("%d",&x),update(i,x);
  //这一行是初始化 更新当前值所有能管理到它的
    while(T --) solve();
    return 0;
}