树 状 数 组 ： 区 间 修 改 ， 区 间 查 询 树状数组 ：区间修改，区间查询 树状数组：区间修改，区间查询
一、树状数组是什么？
新手请参考 — — — — 》 》 ————》》 ————》》
二、区间修改与区间查询
凡是涉及到区间修改，就必须用到 差 分 差分 差分
求前缀和：
- a p a_p ap 的前缀和： ∑ i = 1 p a [ i ] = ∑ i = 1 p ∑ j = 1 i d [ j ] \sum_{i=1}^{p}a[i]=\sum_{i=1}^{p}\sum_{j=1}^{i}d[j] ∑i=1pa[i]=∑i=1p∑j=1id[j]
- 在 ∑ i = 1 p ∑ j = 1 i d [ j ] \sum_{i=1}^{p}\sum_{j=1}^{i}d[j] ∑i=1p∑j=1id[j]中， d 1 d_1 d1 被用了 p p p 次， d 2 d_2 d2 被用了 p − 1 p-1 p−1 次……那么我们可以写出：
- a p a_p ap 的前缀和： ∑ i = 1 p ∑ j = 1 i d [ j ] = ∑ i = 1 p d [ i ] ∗ ( p − i + 1 ) = ( p + 1 ) ∗ ∑ i = 1 p d [ i ] − ∑ i = 1 p d [ i ] ∗ i \sum_{i=1}^{p}\sum_{j=1}^{i}d[j]=\sum_{i=1}^{p}d[i]*(p-i+1)=(p+1)*\sum_{i=1}^{p}d[i]-\sum_{i=1}^{p}d[i]*i ∑i=1p∑j=1id[j]=∑i=1pd[i]∗(p−i+1)=(p+1)∗∑i=1pd[i]−∑i=1pd[i]∗i
- 那么我们可以用树状数组维护两个数组的前缀和：一个数组是 s u m 1 [ i ] = d [ i ] sum1[i]=d[i] sum1[i]=d[i]，另一个数组是 s u m 2 [ i ] = d [ i ] ∗ i sum2[i]=d[i]*i sum2[i]=d[i]∗i
A C c o d e AC code ACcode
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+5;
int n,q,a[maxn],maxx,b[maxn],c[maxn];
/* --------------- fast io --------------- */ // begin
namespace Fread
{
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar()
{
if (S == T)
{
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T)
return '\n';
}
return *S++;
}
} // namespace Fread
namespace Fwrite
{
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush()
{
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c)
{
*S++ = c;
if (S == T)
flush();
}
struct NTR
{
~NTR() { flush(); }
} ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread ::getchar
#define putchar Fwrite ::putchar
#endif
namespace Fastio
{
struct Doublee
{
double x;
int k = 6;
};
struct Reader
{
template <typename T>
Reader &operator>>(T &x)
{
char c = getchar();
T f = 1;
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
x = 0;
while (c >= '0' && c <= '9')
{
x = x * 10 + (c - '0');
c = getchar();
}
x *= f;
return *this;
}
Reader &operator>>(double &num)
{
char in;
double Dec = 0.1;
bool IsN = false, IsD = false;
in = getchar();
if (in == EOF)
{
return *this;
}
while (in != '-' && in != '.' && (in < '0' || in > '9'))
{
in = getchar();
}
if (in == '-')
{
IsN = true;
num = 0;
}
else if (in == '.')
{
IsD = true;
num = 0;
}
else
{
num = in - '0';
}
if (!IsD)
{
while (in = getchar(), in >= '0' && in <= '9')
{
num *= 10;
num += in - '0';
}
}
if (in != '.')
{
if (IsN)
num = -num;
}
else
{
while (in = getchar(), in >= '0' && in <= '9')
{
num += Dec * (in - '0');
Dec *= 0.1;
}
}
if (IsN)
{
num = -num;
}
}
Reader &operator>>(char &c)
{
c = getchar();
while (c == ' ' || c == '\n')
{
c = getchar();
}
return *this;
}
Reader &operator>>(char *str)
{
int len = 0;
char c = getchar();
while (c == ' ' || c == '\n')
{
c = getchar();
}
while (c != ' ' && c != '\n' && c != '\r')
{ // \r\n in windows
str[len++] = c;
c = getchar();
}
str[len] = '\0';
return *this;
}
Reader() {}
} cin;
const char endl = '\n';
struct Writer
{
Writer &operator<<(Doublee op)
{
static int n = pow(10, op.k);
if (op.x == 0)
{
putchar('0'), putchar('.');
for (int i = 1; i <= op.k; ++i)
putchar('0');
return *this;
}
if (op.x < 0)
putchar('-'), op.x = -op.x;
long long y = (long long)(op.x * n) % n;
op.x = (long long)op.x;
cout << op.x;
putchar('.');
int bit[10], p = 0, i;
for (; p < op.k; y /= 10)
bit[++p] = y % 10;
for (i = p; i > 0; i--)
putchar(bit[i] + 48);
return *this;
}
template <typename T>
Writer &operator<<(T x)
{
if (x == 0)
{
putchar('0');
return *this;
}
if (x < 0)
{
putchar('-');
x = -x;
}
static int sta[45];
int top = 0;
while (x)
{
sta[++top] = x % 10;
x /= 10;
}
while (top)
{
putchar(sta[top] + '0');
--top;
}
return *this;
}
Writer &operator<<(char c)
{
putchar(c);
return *this;
}
Writer &operator<<(char *str)
{
int cur = 0;
while (str[cur])
putchar(str[cur++]);
return *this;
}
Writer &operator<<(const char *str)
{
int cur = 0;
while (str[cur])
putchar(str[cur++]);
return *this;
}
Writer() {}
} cout;
} // namespace Fastio
#define cin Fastio ::cin
#define cout Fastio ::cout
#define endl Fastio ::endl
#define Doublee Fastio::Doublee
/* --------------- fast io --------------- */ // end
inline int lowbit(int a)
{
return a&(-a);
}
inline void update(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i))
{
b[i]+=y;
c[i]+=x*y;
}
}
inline void range_update(int l,int r,int x)
{
update(l,x);
update(r+1,-x);
}
inline int query(int x)
{
int ans=0;
for(int i=x;i;i-=lowbit(i))
{
ans += (x+1) * b[i] - c[i];
}
return ans;
}
inline int range_query(int l,int r)
{
return query(r)-query(l-1);
}
signed main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
update(i,a[i]-a[i-1]);
}
for(int i=1;i<=q;i++)
{
int abc,x,y,z;
cin>>abc;
if(abc==1)
{
cin>>x>>y>>z;
range_update(x,y,z);
}
else
{
cin>>x>>y;
cout<<range_query(x,y)<<endl;
}
}
return 0;
}