单点修改，区间查询
很简单，就是运用了前缀和的思想，树状数组裸的板子，不多讲了。
代码
#include <iostream>
#define endl '\n'
#define lowbit(x) (x & -x)
#define R register
using std::cin;
using std::cout;
int n, q;
namespace treeArray
{
const int maxn = 1000006;
long long a[maxn];
inline void add(int pos, int x)
{
for (R int i = pos; i <= n; i += lowbit(i))
a[i] += x;
}
inline long long sum(int pos)
{
long long ans = 0;
for (R int i = pos; i >= 1; i -= lowbit(i))
ans += a[i];
return ans;
}
} // namespace treeArray
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for (R int i = 1, x; i <= n; i++)
{
cin >> x;
treeArray::add(i, x);
}
for (R int i = 1, c, l, r; i <= q; i++)
{
cin >> c >> l >> r;
switch (c)
{
case 1:
treeArray::add(l, r);
break;
case 2:
cout << treeArray::sum(r) - treeArray::sum(l - 1) << endl;
break;
}
}
return 0;
}区间修改，单点查询
[题目]：树状数组 2 ：区间修改，单点查询
我们已经会了树状数组单点修改，区间查询辣，那么，区间修改，单点查询要怎么做呢？
说到区间查询我们能想到前缀和，那么区间修改呢——差分！！！
假设我们要把区间$l\sim r$加上$x$，根据差分的思想，我们只需要把$l\sim n$加上$x$，把$(r+1)\sim n$减去$x$就好了。
假如查询位置$p$的话，我们等于把 $a_1\sim a_p$ 有的值加起来。
也就是 $\sum_{i=1}^{p}a_i$。
我们只需要把树状数组维护的前缀和数组改成差分数组就好了。
代码
#include <iostream>
#define endl '\n'
#define lowbit(x) (x & -x)
#define R register
using std::cin;
using std::cout;
int n, q;
namespace treeArray
{
const int maxn = 1000006;
long long a[maxn];
inline void add(int pos, int x)
{
for (R int i = pos; i <= n; i += lowbit(i))
a[i] += x;
}
inline long long sum(int pos)
{
long long ans = 0;
for (R int i = pos; i >= 1; i -= lowbit(i))
ans += a[i];
return ans;
}
} // namespace treeArray
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for (R int i = 1, x, lx = 0; i <= n; i++) //差分
{
cin >> x;
treeArray::add(i, x - lx); //差分数组存的是两个元素之差
lx = x;
}
for (R int i = 1, c, l, r, x; i <= q; i++)
{
cin >> c >> l;
switch (c)
{
case 1:
cin >> r >> x;
treeArray::add(l, x), treeArray::add(r + 1, -x);
break;
case 2:
cout << treeArray::sum(l) << endl;
break;
}
}
return 0;
}区间修改，区间查询
看到这个标题，您可能会想：什么，树状数组还有这种操作！！！线段树拜拜(。・∀・)ノ。
其实，树状数组也就只能到区间加减这个地步，它是不支持像线段树一样区间求$max$之类的运算的。但是遇到区间加减，区间查询的题目，树状数组还是能爆碾线段树的。
请见下图：
这个东西其实是以区间修改，单点查询为基础的。
回放一下树状数组维护差分数组单点查询的公式：
$$\sum_{i=1}^{p}a_i$$
假如我们查询$1\sim r$的值，我们只能暴力跑这个公式跑$r$遍，也就是：
这个时候，我们发现，$a_1$被算了$r$次，$a_2$被算了$r-1$次，$a_3$被算了$r-2$次……
我们可以得到如下公式：
$$\sum_{i=1}^{r}{\left(r-i+1\right)\times a_i}$$
我们开两个数组，一个存$a_i$，另一个存$a_i \times i$。
我们就可以用这个求辣。
代码
#include <iostream>
using namespace std;
#define R register
#define endl '\n'
#define lowbit(x) x & -x
int n, p;
namespace treeArray
{
const int maxn = 1000006;
long long a1[maxn], a2[maxn];
inline void add(int pos, long long x)
{
for (R int i = pos; i <= n; i += lowbit(i))
a1[i] += x, a2[i] += pos * x;
}
inline long long sum(int pos)
{
long long ans = 0;
for (R int i = pos; i >= 1; i -= lowbit(i))
ans += (pos + 1) * a1[i] - a2[i];
return ans;
}
} // namespace treeArray
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> p;
for (R int i = 1, x, lx = 0; i <= n; i++)
{
cin >> x;
treeArray::add(i, x - lx);
lx = x;
}
for (R int i = 1, c, l, r, x; i <= p; i++)
{
cin >> c >> l >> r;
switch (c)
{
case 1:
cin >> x;
treeArray::add(l, x), treeArray::add(r + 1, -x);
break;
case 2:
cout << treeArray::sum(r) - treeArray::sum(l - 1) << endl;
break;
}
}
return 0;
}
Comments NOTHING