【数据结构】树状数组

普通树状数组维护的信息及运算要满足 结合律 且 可差分，如加法（和）、乘法（积）、异或等．

• 结合律：$(x\ \text{opt} \ y)\ \text{opt}\ z=x\ \text{opt} (y\ \text{opt} \ z)$，其中 $\text{opt}$ 是一个二元运算符．
• 可差分：具有逆运算的运算，即已知 𝑥 ∘𝑦 和 𝑥 可以求出 𝑦．

将有关 $l\ \cdots r$ 的区间询问转化为 $1 \ \cdots r$ 和 $1 \cdots l-1$ 的前缀询问再差分

Luogu P3374 （单点修改&区间求和）

lnk

#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10;
int n,m,a[MAXN];
int lowbit(int x)
{
	return x& -x;
}
struct fenwick
{
	int c[MAXN];
	void modify(int pos,int k)
	{
		a[pos]+=k;
		for(int i=pos;i<=n;i+=lowbit(i))
			c[i]+=k;
	}
	int query(int pos)
	{
		int ans=0;
		for(int i=pos;i>0;i-=lowbit(i))
			ans+=c[i];
		return ans;
	}
	void build()
	{
		memset(c,0,sizeof(c));
		for(int i=1;i<=n;i++)
		{
			c[i]+=a[i];
			int j=i+lowbit(i);
			if(j<=n)c[j]+=c[i];
		}
	}
}qwq;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	qwq.build();
	for(int i=1;i<=m;i++)
	{
		int opt,u,v;
		scanf("%d%d%d",&opt,&u,&v);
		if(opt==1)
			qwq.modify(u,v);
		else printf("%d\n",qwq.query(v)-qwq.query(u-1));
	}
	return 0;
}

Luogu P3368 （区间修改&单点求值）

#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10;
int n,m,a[MAXN];
int lowbit(int x)
{
    return x& -x;
}
struct fenwick
{
    long long c[MAXN];
    void modify(int pos,int k)
    {
        for(int i=pos;i<=n;i+=lowbit(i))
            c[i]+=k;
    }
    long long query(int pos)
    {
        long long ans=0;
        for(int i=pos;i>0;i-=lowbit(i))
            ans+=c[i];
        return ans;
    }
    void build()
    {
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)
        {
            modify(i,a[i]-a[i-1]);
        }
    }
}qwq;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    qwq.build();
    for(int i=1;i<=m;i++)
    {
        int opt;
        scanf("%d",&opt);
        if(opt==1)
        {
            int x,y,k;
            scanf("%d%d%d",&x,&y,&k);
            qwq.modify(x,k);
            qwq.modify(y+1,-k);
        }
        else
        {
            int pos;
            scanf("%d",&pos);
            printf("%lld\n",qwq.query(pos));
        }
    }
    return 0;
}

以上两个题目在loj有相同的题目(#130、#131)

Loj #132 （区间修改&区间求和）

//Loj 132 区间修改&区间求和
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e6+10;
int n,m,a[MAXN];
int lowbit(int x)
{
	return x&-x;
}
struct fenwick
{
	int c[MAXN];
	void modify(int pos,int val)
	{
		for(int i=pos;i<=n;i+=lowbit(i))
			c[i]+=val;
	}
	int query(int pos)
	{
		int ans=0;
		for(int i=pos;i>0;i-=lowbit(i))
			ans+=c[i];
		return ans;
	}
}qwq1,qwq2;
int pre_sum(int x)
{
	return (x+1)*qwq1.query(x)-qwq2.query(x);
}
int query(int l,int r)
{
	return pre_sum(r)-pre_sum(l-1);
}
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0',c=getchar();}
	return x*f;
}
signed main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)
	{
		int d=a[i]-a[i-1];
		qwq1.modify(i,d);
		qwq2.modify(i,d*i);
	}
	for(int i=1;i<=m;i++)
	{
		int opt=read();
		if(opt==1)
		{
			int l=read(),r=read(),val=read();
			qwq1.modify(l,val);
			qwq1.modify(r+1,-val);
			qwq2.modify(l,val*l);
			qwq2.modify(r+1,-val*(r+1));
		}
		else
		{
			int l=read(),r=read();
			printf("%lld\n",query(l,r));
		}
	}
	return 0;
}