根据我们多年的经验，BIT是个常数小，维护区间的好东西。

但似乎只能维护单点修改+区间查询(？？若真是这样，那我写这篇博文有什么用?->所有东西必有其存在意义)
下面先给出最基本的BIT Code:

#define lowbit(x) ((x)&(-(x)))
void update(ll *a,int p,int val)
{
	for(int i=p;i<=n;i+=lowbit(i))
	{
		a[i]+=val;
	}
}
ll query(ll *a,int p)
{
	ll ret=0;
	for(int i=p;i>0;i-=lowbit(i))
	{
		ret+=a[i];
	}
	return ret;
}

update 修改某点的值，query查询[1，i]的和，赤裸裸的单点修改+区间查询。
但我们如果想维护区间修改，怎么办？

差分

差分是个神奇的东西，它让BIT变得高级，使zkw浮于云端之上，令……

区间修改+单点查询

若有一天，我心血来潮，想让BIT变幻一下。

直至今日，你火上浇油，送来差分药水一罐。

首先，我们可以(构)造一数组 $b$ ，使得 $b_i= a_i - a_{i-1} $ (a为原数组且 $a_0=0$ )，则:

$$a_x= \sum_{i=1}^x b_i$$

即原数组的某点值=query(b,i);

那么如何区间修改？

给一段区间加上一个数，区间的差分数组b并没有变，变的只有两点的值—>b[l]和b[r+1];

$$b_l += val;$$ $$b_{r+1}-=val$$

至此，BIT成功倒置。

例题传送门

Code:

//BIT+差分 --> 区间修改+单点查询
#include<iostream>
#include<cstdio>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
ll sum[maxn]={0},x=0,y=0;
int n,q;
void update(int,int);
void UP(int,int,int);
ll query(int);
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		y=x;
		scanf("%lld",&x);
		update(i,x-y);
	}
	scanf("%d",&q);
	while(q--)
	{
		int a,b,c;
		scanf("%d",&c);
		if(c==2) scanf("%d",&a),printf("%lld\n",query(a));
		else scanf("%d%d%d",&a,&b,&c),UP(a,b,c);
	}
	return 0;
}
void update(int p,int val)
{
	for(int i=p;i<=n;i+=lowbit(i))
	{
		sum[i]+=val;
	}
}
ll query(int p)
{
	ll ret=0;
	for(int i=p;i>0;i-=lowbit(i))
	{
		ret+=sum[i];
	}
	return ret;
}
void UP(int l,int r,int val)
{
	update(l,val);
	update(r+1,-val);
}

区间修改+区间查询

真有一天，我突发奇想，欲饮BIT茶一杯。

如至今日，你雪中送C，赠予差分药水一桶。

首先，我们还是要(构)造一个数组add，add[i]表示区间[i，n]的共同增量，那么:

$$\begin{array}\\ sum_i &= a_1+L+a_i+add_1 \times i+add_2 \times (i-1)+L+add_i \times 1 \\ &= \sum_{x = 1}^i a_x + \sum_{x = 1}^i {add_x \times (i+1-x)} \\ &= \sum_{x = 1}^i a_x + (i+1) \times (\sum_{x = 1}^i {add_x}) - (\sum_{x = 1}^i {add_x \times x}) \\ \end{array}$$

其中前缀和$\sum_{x=1}^i a_x$可以预处理出来，那么我们只需要维护$add_i$和$add_i \times i$就可以在$O(logn)$的时间范围内得到正确解。

那么如何维护？

很简单，转化后对这两个数组的操作就是区间修改+单点查询，用上面的方法就行了。

例题传送门

Code:

//BIT+差分 --> 区间修改+区间查询
#include<iostream>
#include<cstdio>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
ll sum[maxn]={0},add[maxn]={0},addS[maxn]={0},n,q;
void update(ll*,int,int);
ll query(ll*,ll);
ll getsum(int,int);
void UP(int,int,int);
int main()
{
	int x;
	char op[5];
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		sum[i]=sum[i-1]+x;
	}
	while(q--)
	{
		int a,b,c;
		scanf("%s",op);
		if(op[0]=='Q') scanf("%d%d",&a,&b),printf("%lld\n",getsum(a,b));
		else scanf("%d%d%d",&a,&b,&c),UP(a,b,c);
	}
	return 0;
}
void update(ll *a,int p,int val)
{
	for(int i=p;i<=n;i+=lowbit(i))
	{
		a[i]+=val;
	}
}
ll query(ll *a,int p)
{
	ll ret=0;
	for(int i=p;i>0;i-=lowbit(i))
	{
		ret+=a[i];
	}
	return ret;
}
void UP(int l,int r,int val)
{
	update(add,l,val);
	update(add,r+1,-val);
	update(addS,l,val*l);
	update(addS,r+1,-val*(r+1));
}
ll getsum(int l,int r)
{
	return (sum[r]-sum[l-1])+((r+1)*query(add,r)-l*query(add,l-1))-(query(addS,r)-query(addS,l-1));
}

BIT的基础变幻到此结束，欢迎各位dalao指出不足。

穿过时空的大门，勇敢的拿起BIT吧！