专栏文章

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

lliyao2025
P3374题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipk8nxe
此快照首次捕获于
2025/12/03 13:22
3 个月前
此快照最后确认于
2025/12/03 13:22
3 个月前
查看原文

题意：

有一个由 nn 个数字组成的数列，对这个数列进行 mm 次操作：
  • 将第 xx 个数加 kk。
  • 输出 [x,y][x,y] 区间内的和。

树状数组

引入

一个包含n个数的序列 2,7,1,12,5,9,…,2,7,1,12,5,9,\dots, 计算前 ii 个数的和值，称为前缀和。
sum[i]=a[1]+a[2]+,…,+a[i](i=1,2,…,n)sum[i]=a[1]+a[2]+,\dots,+a[i](i=1,2,\dots,n)。
累加求前 nn 个数的和值需要 O(n)O(n) 时间。而且若对 a[i]a[i] 进行修改，则 sum[i],sum[i+1],…,sum[n]sum[i],sum[i+1],\dots,sum[n] 都需要修改，最坏的情况下需要 O(n)O(n) 时间。
树状数组可以高效实现，其查询前缀和与点更新均为 O(log⁡n)O(\log n)。
那么树状数组是如何巧妙地实现呢？

正文

树状数组引入了分级管理制度，设置一个管理小组，每个管理员管理一个或多个连续的元素。例如，数列有 99 个元素，分别用 a[1],a[2],…,a[9]a[1],a[2],\dots,a[9] 存储，管理数组为 c[]c[]。管理数组 c[]c[] 是树状的，因此称为树状数组。
树状数组，又称为二进制索引树 (BinaryIndexedTrees)(Binary Indexed Trees)，通过二进制分解划分区间。那么 c[i]c[i] 存储的是哪些值？

1.区间长度

若 ii 的二进制表示末尾有 kk 个连续的 00，则 c[i]c[i] 存储的区间长度为 2k2^k，从 a[i]a[i] 向前数 2k2^k 个元素，即 c[i]=s[i−2k+1]+s[i−2k+2]+,…,+a[i]c[i]=s[i-2^k+1]+s[i-2^k+2]+,\dots,+a[i]。
举例：
  • c[6]=a[5]+a[6]c[6]=a[5]+a[6]
  • c[12]=a[9]+a[10]+a[11]+a[12]c[12]=a[9]+a[10]+a[11]+a[12]，即管理 lowbit(12)⁡\operatorname{lowbit(12)} 个。

2.前驱和后继

  • 直接前驱： c[i]c[i] 的直接前驱为 c[i−lowbit(i)⁡]c[i-\operatorname{lowbit(i)}]，即 c[i]c[i] 左侧紧邻的子树的根。
  • 直接后继：c[i]c[i] 的直接后继为 c[i+lowbit(i)⁡]c[i+\operatorname{lowbit(i)}]，即 c[i]c[i] 的父节点。
  • 前驱：c[i]c[i] 左侧所有子树的根。
  • 后继：c[i]c[i] 的所有祖先。

3.查询前缀和

前 ii 个元素的前缀和 sum[i]sum[i] 等于 c[i]c[i] 加上 c[i]c[i] 的前驱。 sum[7]sum[7] 等于 c[7]c[7] 加上 c[7]c[7] 的前驱，sum[7]=c[7]+c[6]+c[4]sum[7]=c[7]+c[6]+c[4]。

4.点更新

 若对 a[i]a[i] 进行修改。
  • 令 a[i]a[i] 加上一个数 zz，则只需更新 c[i]c[i] 及其后继（祖先）。
  • 即令这些节点都加上 zz 即可，无需修改其他节点。
例如，修改 a[5]a[5]，令其加 22。只需 c[5]+2c[5]+2，然后 c[5]c[5] 的后继分别加 22，即 c[6]+2,c[8]+2,c[16]+2,c[32]+2,…c[6]+2,c[8]+2,c[16]+2,c[32]+2,\dots。

5.查询区间和

若求区间和值 a[i]+a[i+1]+,…,+a[j]a[i]+a[i+1]+,\dots,+a[j]，则求解前 jj 个元素的和值减去前 i−1i-1 个元素的和值即可。即 sum[j]−sum[i−1]sum[j]-sum[i-1]。

思路

套模板就行。
CPP
#include<bits/stdc++.h>
using namespace std;
long long m,n,x,y,z;
long long a[1000005],c[1000005];
long long lowbit(long long i)//求lowbit
{
    return (-i)&i;
}
void add(long long i,long long z)//添加操作
{
    for(;i<=n;i+=lowbit(i))
    c[i]=c[i]+z;
} 
long long sum(long long i)//求和操作
{
    long long s=0;
    for(;i>0;i-=lowbit(i))
    s+=c[i];
    return s;
} 
int main(){
    scanf("%lld%lld",&n,&m);//输入
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        add(i,a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&z,&x,&y);
        if(z==1)add(x,y);
        else printf("%lld\n",sum(y)-sum(x-1));//求区间和，输出
    }
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...