树状数组：
利用数组下标的二进制关系，构造一种类似于树形的结构，有点像一个变成树形的前缀和
可以实现单点修改、区间修改、区间查询等操作
2的整数n次幂的位置就是表示该位置及之前所有数之和
在2的整数n次幂上加上小于等于2的n次幂的2的k次幂的数，也表示2^n +1 ··· 2^n + 2^k区间内的整数和
故查询时区间拼凑即可 logn次
lowbit(x):取出x的最低位的一，区间拼凑时，拼一即可
example：（二进制）
1
10
11
100
101
110
111
1000
由一的数量以及位置决定该点存储的区间
查询区间和时，只需将对应的一（基本是log个）的位置所对应的值加起来即可,利用 +lowbit
区间修改时，需要修改本身位置的同时，再修改对应的相关区间，利用 -lowbit
My_Code:
//树状数组1 luoguP3374
#include<bits/stdc++.h>
using namespace std;
int lowbit(int x) {
return x&(-x);
}
int update(int x,int k) {
while(x<=n) {
tree[x]+=k;
x+=lowbit(x);
}
}
int query(int x){
int ans=0;
while(x){
ans+=tree[i];
x-=lowbit(x);
}
return ans;
}
int n;
int tree[100001];
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&tree[i]);
}
for(int i=1;i<=m;i++){
int op;
scanf("%d",&op);
if(op==1){
int x,k;
scanf("%d%d",&x,&k);
update(x,k);
}
if(op==2){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",query(r)-query(x-1));
}
}
return 0;
}
//树状数组1 luoguP3368
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll read(){
ll x=0,f=1;
char ch=getchar();
while(ch<48||ch>57){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>=48&&ch<=57){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
ll lowbit(ll x){
return x&-x;
}
ll a[N],b[N],c[N],n,m;
void update(ll x,ll d){
ll p=x;
while(x<=n){
b[x]+=d;
c[x]+=(p-1)*d;
x+=lowbit(x);
}
}
ll sum(ll x){
ll ans=0,p=x;
while(x){
ans+=p*b[x]-c[x];
x-=lowbit(x);
}
return ans;
}
int main() {
n=read();
m=read();
for(ll i=1;i<=n;i++){
a[i]=read();
update(i,a[i]-a[i-1]);
}
for(ll i=1;i<=m;i++){
ll op=read();
if(op==1) {
ll x=read(),y=read(),k=read();
update(x,k);
update(y+1,-k);
}
else {
ll x=read();
printf("%lld\n",sum(x)-sum(x-1));
}
}
return 0;
}
//线段树1 luoguP3372 树状数组写法
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll read(){
ll x=0,f=1;
char ch=getchar();
while(ch<48||ch>57){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>=48&&ch<=57){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
ll lowbit(ll x){
return x&-x;
}
ll a[N],b[N],c[N],n,m;
void update(ll x,ll d){
ll p=x;
while(x<=n){
b[x]+=d;
c[x]+=(p-1)*d;
x+=lowbit(x);
}
}
ll sum(ll x){
ll ans=0,p=x;
while(x){
ans+=p*b[x]-c[x];
x-=lowbit(x);
}
return ans;
}
int main() {
n=read();
m=read();
for(ll i=1;i<=n;i++){
a[i]=read();
update(i,a[i]-a[i-1]);
}
for(ll i=1;i<=m;i++){
ll op=read();
if(op==1) {
ll x=read(),y=read(),k=read();
update(x,k);
update(y+1,-k);
}
else {
ll x=read(),y=read();
printf("%lld\n",sum(y)-sum(x-1));
}
}
return 0;
}