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

_Z_YX_ · 2025-04-18 07:29:10 · 题解

模板1

题目大意：

有一个由 n 个数字组成的数列，对于第 i 个数其初始值为 i，对这个数列进行 m 次操作：

• 操作1：将第 x 个数加 k。

• 操作2：输出 a 数组中 [x,y] 区间内的和，包括 a[x] 和 a[y]。

算法分析：

由于 n 和 m 的范围均为 5 \times 10^5，因此暴力绝对不可取，考虑使用树状数组解决。

关于树状数组：

1. 简介：树状数组的学名是二叉搜索树，其利用二叉树思想的前缀和的加强版。

2. 与二叉树的区别：简单来说，树状数组比二叉树少了大部分非叶子节点的子节点。以下两幅图帮助理解：

   （1）一个倾斜的二叉树

   （2）其对应的树状数组

   观察后可发现，一个二叉树如果只保留每一列最上面的一个节点，就是其对应的树状数组。

3. 在本题的运用：单点修改，区间查询。

介绍一个新的概念，lowbit：

• 对于一个正整数 x，我们规定 lowbit(x) 为：二进制表示的 x，除最后一位 1 外，其余全部改为 0，所得到的数。

• 一般将 lowbit(i) 用于求 a[i] 的父节点。

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

Code:

#include<bits/stdc++.h>
using namespace std;
int n,m,a[500005],c[500005];
inline int lowbit(int x){
    return x&(-x);
}
void add(int i,int x){//将第i个数增加x。
    while(i<=n){
        c[i]+=x;
        i+=lowbit(i);
    }
}
int query(int x){//求a[x]到a[y]的区间和。
    int s=0;
    while(x){
        s+=c[x];
        x-=lowbit(x);
    }
    return s;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        add(i,a[i]);//为每个结点赋初值。
    }
    int op,x,y;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&op,&x,&y);
        if(op==1){//将a[x]的值加y。
            a[x]+=y;
            add(x,y);
        }else{
            printf("%d\n",query(y)-query(x-1));//输出区间和。
        }
    }
    return 0;
}