树状数组，
1，单点修改，区间查询；例题
code：
主要操作：
int lowbit(int x)
{
return x&(-x);
}
void build(int x,int k)
{
for(int i=x; i<=n; i+=lowbit(i))
tree[i]+=k;
}
int quary(int x)
{
int ans=0;
for(int i=x; i>=1; i-=lowbit(i))
ans+=tree[i];
return ans;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+10;
int a[maxn],tree[maxn];
int n,m;
int lowbit(int x)
{
return x&(-x);
}
void build(int x,int k)
{
for(int i=x; i<=n; i+=lowbit(i))
tree[i]+=k;
}
int quary(int x)
{
int ans=0;
for(int i=x; i>=1; i-=lowbit(i))
ans+=tree[i];
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++)
{
cin>>a[i];
build(i,a[i]);
}
while(m--)
{
int k,x,y;
cin>>k>>x>>y;
if(k==1)
build(x,y);
else
{
cout<<quary(y)-quary(x-1)<<endl;
}
}
//system("pause");
return 0;
}
2，区间修改，单点查询：（差分思想）例题：
if(k==1)
{
cin>>y>>z;
build(x,z);
build(y+1,-z);
}
else
{
cout<<a[x]+quary(x)<<endl;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+10;
ll a[maxn],tree[maxn];
ll n,m;
ll lowbit(ll x)
{
return x&(-x);
}
void build(ll x,ll k)
{
for(ll i=x; i<=n; i+=lowbit(i))
tree[i]+=k;
}
ll quary(ll x)
{
ll ans=0;
for(ll i=x; i>=1; i-=lowbit(i))
ans+=tree[i];
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++)
{
cin>>a[i];
}
while(m--)
{
ll k,x,y,z;
cin>>k>>x;
if(k==1)
{
cin>>y>>z;
build(x,z);
build(y+1,-z);
}
else
{
cout<<a[x]+quary(x)<<endl;
}
}
//system("pause");
return 0;
}
原文链接: https://www.cnblogs.com/sweetlittlebaby/p/12748553.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/343642
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
