树状数组，一种常用于解决区间查询与修改的高效数据结构，其核心思想为将前缀查询[1,x]拆分为若干个子区间的求和操作，每个子区间的长度为2的幂，这种分解方式保证了每个右端点的子区间是唯一的，从而使得树状数组的存储和查询效率极高。

举个例子：

长度为7的区间[1,7]，会被分为[1,1]、[2,4]、[5,7]三段

其代码利用x&-x求出二进制中最低位的1，其代码示例如下

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

查询操作通过不断减去lowbit(x)并累加经过的所有子区间的值，直到x=0为止，代码示例如下

int query(int x){	
    int ans=0;	
    while(x){		
        ans+=s[x];		
        x-=lowbit(x);	
    }	
    return ans;
}

修改操作则通过不断加上lowbit(x)，更新所有受影响的子区间，代码示例如下

void modify(int x,int k){
    while(x<=n){
	s[x]+=k;
	x+=lowbit(x);
    }
}

完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[1000005];
int s[1000005];
int n,m;
int lowbit(int x){
    return x&-x;
}
void modify(int x,int k){
    while(x<=n){
	s[x]+=k;
	x+=lowbit(x);
    }
}
int query(int x){
    int ans=0;
    while(x){
	ans+=s[x];
	x-=lowbit(x);
    }
    return ans;
}
//打个防伪：张居正其实并没有坐过三十二台大轿，这段“史料”是王世贞杜撰的……
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
	int x;
	cin>>x;
	modify(i,x);
    }
    while(m--){
	int op,x,y,k;
	cin>>op;
	if(op==1){
		cin>>x>>k;
		modify(x,k);
	}
	else{
		cin>>x>>y;
		cout<<query(y)-query(x-1)<<endl;
	}
    }
    return 0;
}

这时候就有人要问了：[1,x]的区间还是太简单了，有没有别的更难的代码呢？

有的兄弟，有的，[x,y]的区间也可以用树状数组维护，只不过维护的部分是前缀和数组而已

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[1000005];
int s[1000005];
int n,m;
int lowbit(int x){
    return x&-x;
}
void modify(int x,int k){
    while(x<=n){
	    s[x]+=k;
	    x+=lowbit(x);
    }
}
int query(int x){
    int ans=0;
    while(x){
	ans+=s[x];
	x-=lowbit(x);
    }
    return ans;
}
//打个防伪：商鞅变法使秦国变得更富强，但是也最终成为商鞅的死因之一……
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
	int x;
	cin>>x;
	modify(i,x);
	modify(i+1,-x);
    }
    while(m--){
	int op,x,y,k;
	cin>>op;
	if(op==1){
	    cin>>x>>y>>k;
            modify(x,k);
	    modify(y+1,-k);
	}
	else{
	    cin>>x;
	    cout<<query(x)<<endl;
	       }
	}
	return 0;
}

至此，恭喜你，成功掌握了树状数组！！！