树状数组的高级操作

发布于 2019-11-12  297 次阅读


单点修改,区间查询

题目:树状数组 1:单点修改,区间查询

很简单,就是运用了前缀和的思想,树状数组裸的板子,不多讲了。

代码

#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;
}

区间修改,区间查询

题目:树状数组 3 :区间修改,区间查询

看到这个标题,您可能会想:什么,树状数组还有这种操作!!!线段树拜拜(。・∀・)ノ。

其实,树状数组也就只能到区间加减这个地步,它是不支持像线段树一样区间求$max$之类的运算的。但是遇到区间加减,区间查询的题目,树状数组还是能爆碾线段树的。

请见下图:

这个东西其实是以区间修改,单点查询为基础的。

回放一下树状数组维护差分数组单点查询的公式:

$$\sum_{i=1}^{p}a_i$$

假如我们查询$1\sim r$的值,我们只能暴力跑这个公式跑$r$遍,也就是:

i=1rj=1iaj

这个时候,我们发现,$a_1$被算了$r$次,$a_2$被算了$r-1$次,$a_3$被算了$r-2$次……

我们可以得到如下公式:

$$\sum_{i=1}^{r}{\left(r-i+1\right)\times a_i}$$

=i=1r(r+1)×aii=1rai×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;
}

$ end $