树状数组模板：洛谷P3374，P3368

本文主要是介绍树状数组模板：洛谷P3374，P3368，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
P3374
更新单点值，求区间和
输入 #1
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
输出 #1
14
16
AC代码：

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=5e5+5;
long long sum[MAXN],n,m;
void add(long long x,long long d)
{while(x<=MAXN){sum[x]+=d;x+=lowbit(x);}
}
int ask(long long x)
{long long res=0;while(x){res+=sum[x];x-=lowbit(x);}return res;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){long long tmp;cin>>tmp;add(i,tmp);}for(int i=1;i<=m;i++){long long x,y,z;cin>>x>>y>>z;if(x==1) add(y,z);else cout<<ask(z)-ask(y-1)<<endl;}return 0;
}

P3368
更新区间值，求单点值
输入 #1
5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4
输出 #1
6
10
AC代码：

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=5e5+5;
long long sum[MAXN];
long long p[MAXN];
void add(long long x,long long d)
{while(x<=MAXN){sum[x]+=d;x+=lowbit(x);}
}
int ask(long long x)
{long long ans=0;while(x){ans+=sum[x];x-=lowbit(x);}return ans;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);long long n,m;cin>>n>>m;for(int i=1;i<=n;i++) cin>>p[i];for(int i=1;i<=m;i++){int a;cin>>a;if(a==1){int x,y,z;cin>>x>>y>>z;add(x,z),add(y+1,-z);}if(a==2){int x;cin>>x;cout<<p[x]+ask(x)<<endl;}}return 0;
}

总结：
在这里插入图片描述
对于某个儿子单点的修改，它的父亲以及所有的间接父亲都会有相应的修改，即add(x,y)的操作只是修改了第x个单点，但是x之后的所有ask（前缀和）都会修改y。
但区间修改其实并不是直接在原区间修改，而是让原区间的某个点加上修改后的ask，，啊啊啊啊啊，有点抽象，不怎么好描述，还是需要细细思考。。