树状数组：单点修改与区间和

算法理解

lowbit(x) 取下标最低位的 1，树状数组节点保存一段固定长度的和。更新时向上影响所有包含该位置的区间；查询时不断拆掉最低位，组合成前缀和。

• 复杂度：单点更新、前缀和均 O(log n)。
• 注意：下标必须从 1 开始；区间和为 sum(r) - sum(l - 1)。

模板代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) (x&(-x))
const int N = 1e5 + 10;
int c[N];  
int getsum(int x)
{
	int ans=0;
	for (int i=x;i>=1;i-=lowbit(i))
	{
		ans+=c[i];
	}
	return ans;
}
void updata(int x,int v)
{
	for (int i=x;i<=N;i+=lowbit(i))
	{
		c[i]+=v;
	}
}
void solve()
{

}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t=1;
//	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}