前言

简介：涉及树状数组，题目源于洛谷
建议大家先自行尝试解题，同时阿鑫的水平不高，所以题解也通常并不算好，建议大家可以在洛谷相关题目的题解处查看其他大佬的题解，阿鑫的题解简单看看就好。

树状数组,常用于需要 区间（单点）修改，区间（单点）查询。

lowbit（x）：取得x最低位1的值，如 lowbit(6)=lowbit((110)₂)=(10)₂

lowbit常用实现方法为 x&-x

原理分析：计算机数据是以补码的形式存储的。

模板题

洛谷P3374 【模板】树状数组 1

题目链接：洛谷P3374 【模板】树状数组 1

题目描述
如题，已知一个数列，你需要进行下面两种操作：

• 将某一个数加上 x
  
• 求出某区间每一个数的和
  

输入格式
第一行包含两个正整数 n,m，分别表示该数列数字的个数和操作的总个数。
第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。
接下来 m 行每行包含 3 个整数，表示一个操作，具体如下：

• 1 x k 含义：将第 x 个数加上 k
  
• 2 x y 含义：输出区间 [x,y] 内每个数的和
  

输出格式
输出包含若干行整数，即为所有操作 2 的结果。
输入输出样例
输入

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

输出

14
16

说明/提示

【数据范围】

对于 30% 的数据，1≤n≤8，1≤m≤10；
对于 70% 的数据，1≤n,m≤10⁴；
对于 100% 的数据，1≤n,m≤5×10⁵。

解题思路：

ac题解

//时间：512ms(O2:428ms) 内存：2.31MB
#include <bits/stdc++.h>
using namespace std;

int n,m,ans;
int tr[500005];
#define lowbit(x) ((x)&-(x))

void update(int x,int y,int n){
    int i;
    for(i=x;i<=n;i+=lowbit(i)){
        tr[i]+=y;
    }
}
int mysum(int x){
    int i,sum=0;
    for(i=x;i>0;i-=lowbit(i)){
        sum+=tr[i];
    }
    return sum;    
}

int main()
{
    cin>>n>>m;
    int i,j,t;
    for(i=1;i<=n;i++){
        scanf("%d",&t);
        update(i,t,n);
    }    
    while(m--){
        scanf("%d%d%d",&t,&i,&j);
        if(t==1){
            update(i,j,n);
        }else if(t==2){
            ans=mysum(j)-mysum(i-1);
            printf("%d\n",ans);
        }
    }
    return 0;
}

P3368 【模板】树状数组 2

题目链接：洛谷P3368 【模板】树状数组 2
解题思路：

ac题解