樹狀數組區間加法區間查

區間加法就是差分

區間查詢需要維護另外另一個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;
}