区间加法就是差分
区间查询需要维护另外另一个BIT
\[\begin{align}
&=\sum_{i=1}^r a_i \&=\sum_{i=1}^r \sum_{j=1}^{i} b_j \&=\sum_{i=1}^r b_i \times (r-i+1) \&=\sum_{i=1}^r b_i \times (r+1) -\sum_{i=1}^r b_i \times i
\end{align}
\]
维护两个BIT，\(\sum b_i,\sum i*b_i\)
#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
#define drp(i,j,k) for(register int i(j);i>=k;--i)
using namespace std;
#define int long long
//#define gt getchar
inline char gt()
{
static char buf[1 << 21], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void read (T &x)
{
register char ch = gt();
x = 0;
int w(0);
while(!(ch >= ‘0‘ && ch <= ‘9‘)) w |= ch == ‘-‘, ch = gt();
while(ch >= ‘0‘ && ch <= ‘9‘) x = x * 10 + (ch & 15), ch = gt();
w ? x = ~(x - 1) : x;
}
template <typename T >
inline void out(T x)
{
if(x < 0) x = -x, putchar(‘-‘);
char ch[20];
int num(0);
while(x || !num) ch[++num] = x % 10 + ‘0‘, x /= 10;
while(num) putchar(ch[num--]);
putchar(‘\n‘);
}
const int MAX = 1e6 + 79;
int N, Q;
int sum1[MAX], a, b,sum2[MAX];
inline int lowbit(int x)
{
return (x & -x);
}
inline void add(int x, int val)
{
int mul=x;
for(; x <= N; x += lowbit(x)) sum1[x] += val,sum2[x]+=val*mul;
}
//sum1[i] = D[i]￡?sum2[i] = D[i]*(i);
inline int getnum(int x)
{
int res = 0,mul=x;
for(; x; x -= lowbit(x)) res += sum1[x]*(mul+1)-sum2[x];
return res;
}
signed main()
{
read(N);
read(Q);
rep(i, 1, N)
{
read(a), add(i, a - b);
b = a;
}
int op = 0, x, y, z;
rep(i, 1, Q)
{
read(op);
if(op == 1)
{
read(x);
read(y);
read(z);
add(x, z);
add(y + 1, -z);
}
else
{
read(x);read(y);
out(getnum(y)-getnum(x-1));
}
}
return 0;
}