题解 P3368 【【模板】树状数组 2】

Hexarhy · 2020-02-14 14:58:31 · 题解

逛了一圈题解，发现大都没有合格的思路讲解和 \LaTeX 的应用。

这里来补发一篇，顺便涨咕值。

本篇题解将把重心偏向为什么且如何通过差分来实现本题要求，因而将淡化甚至略过树状数组的相关知识。

有关树状数组的详情请看这里。

解题思路

前置知识：

树状数组入门。详情点这里。本题是一个小小的拓展而已。
差分基础知识。

我们知道，普通的树状数组维护的是一个前缀和数组，支持单点修改和区间查询。

但是这道题目，要我们实现区间修改和单点查询。

对于区间修改，有一种很暴力思路是：

遍历 [L,R] 的区间，每次进行一次单点修改。

然而时间复杂度最劣为 O(n^2\log n)，显然这是会超时的。

想到这，学过的同学就能很敏感的想到，差分可以轻松解决。

提示：下面大部分内容关于差分。若您已经非常熟悉请跳过。

举个例子：记差分数组为 T。

原来的序列为：

1	2	3	4	5

差分数组为：

1	1	1	1	1

在 [2,4] 之间 +2，则序列为：

1	4	5	6	5

差分数组变为：

1	3	1	1	-1

对比发现，只有 T_2+2，以及 T_5-2。只用了两次单点修改。

推广一下：

对于序列 a_1,a_2,a_3,\cdots,a_n，在区间 [L,R] 内加上 \Delta，不难发现：

而 T_L=a_L-a_{L-1}，a_{L-1} 大小不变，只有 a_L 增加了 \Delta，因此 T_L 增加了 \Delta。同理，T_{R+1} 减少 \Delta。

通过上述方法，就可以实现只修改 T_L 和 T_{R+1} 共两次就完成了 [L,R] 的区间修改。时间复杂度大大降低。

我们只需用树状数组维护这个 T 就可以了。

但是对于单点查询，需要略微改动。

我们直接输出query(x)即可，因为a_x=\sum^x_{i=1}T_i，而树状数组询问恰好是差分数组的前缀和。

时间复杂度依然为 O(n\log n)。

其它方法

模板题自然有很多解法，这里顺带一提。详情请看其它题解。

分块。
线段树。
差分。
~~cdq分治。~~

参考代码

其实也就是略加改动。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN=6e5+5;
int n,m;
int tree[MAXN],a[MAXN];

inline int lowbit(const int x)
{
    return x&(-x);
}

void modify(int x,const int k)
{
    while(x<=n)
    {
        tree[x]+=k;
        x+=lowbit(x);
    }
}

int query(int x)
{
    int res=0;
    while(x)
    {
        res+=tree[x];
        x-=lowbit(x);
    }
    return res;
}
//以上都是树状数组模板
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        modify(i,a[i]-a[i-1]);//a[i]-a[i-1]就是求差分数组
    }
    for(int i=1;i<=m;i++)
    {
        int opt,x,y,k;
        cin>>opt>>x;
        if(opt==1)
        {
            cin>>y>>k;
            modify(x,k);
            modify(y+1,-k);//修改两次差分数组，就完成区间修改序列
        }
        if(opt==2)
         cout<<query(x)<<endl;//直接输出即可，原因说过
    }
    return 0;
}