P3372 【模板】线段树 1【题解2】

本题题解分两篇
此篇为第贰篇，用树状数组做
第壹篇：P3372 【模板】线段树 1【题解1】

本文讲解树状数组解决区间修改+区间查询

其它树状数组相关文章：

• 树状数组讲解+单点修改/查询
• 树状数组解决区间修改+单点查询

P3372 【模板】线段树 1

题目描述

如题，已知一个数列 { a i } \{a_i\} {ai​}，你需要进行下面两种操作：

1. 将某区间每一个数加上 $k$。
2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 $n,m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数 $a_i$，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

1. 1 x y k：将区间 $[x,y]$ 内每个数加上 $k$。
2. 2 x y：输出区间 $[x,y]$ 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

样例 #1

样例输入 #1

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

样例输出 #1

11
8
20

提示

对于 $15\%$ 的数据：$n\le 8$，$m\le 10$。
对于 $35\%$ 的数据：$n\le {10}^3$，$m\le {10}^4$。
对于 $100\%$ 的数据：$1\le n,m\le {10}^5$，$a_i,k$ 为正数，且任意时刻数列的和不超过 $2\times 10^{18}$。

【样例解释】

解析

谁说线段树模板题就要用线段树的？[狗头]
如果用树状数组做的话，本质就是区间修改+区间查询

结论与证明

设$d[]$是原数组$a[]$的差分数组，$s_n$是原数组a[0]~a[n]的和
结论：$s_n=(n+1)\ast (b[1]+b[2]+b[3]+\dots +b[n])-(b[1]+2\ast b[2]+3\ast b[3]+\dots +n\ast b[n])$
证明：
$s_n$

$=a[1]+a[2]+a[3]+\dots +a[n]$

$=b[1]+(b[1]+b[2])+(b[1]+b[2]+b[3])+\dots +(b[1]+b[2]+b[3]+\dots +b[n])$

$=n\ast b[1]+(n-1)\ast b[2]+(n-2)\ast b[3]+\dots +b[n]$

$=(n+1)\ast (b[1]+b[2]+b[3]+\dots +b[n])-(b[1]+2\ast b[2]+3\ast b[3]+\dots +n\ast b[n])$

结论的使用

由于是差分数组，每次原数组的区间修改它只需变两个点的值
差分数组值变了，$b[1]+b[2]+b[3]+\dots +b[n]$和$b[1]+2\ast b[2]+3\ast b[3]+\dots +n\ast b[n]$的值都会改变
这可以用树状数组维护。
具体结合代码解释

完整代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1000005;
int n,m;
int lowbit(int x){return x&(-x);
}
//a为原数组，b为差分数组，d为维护b[1]~b[i]的和的树状数组，t为维护b[1]*1~b[i]*i的和的树状数组
int d[MAXN],t[MAXN],a[MAXN],b[MAXN];
int get(int x){int u=0,v=0;for(int i=x;i;i=i-lowbit(i)){u+=t[i];v+=d[i];}return (x+1)*u-v;//结论的使用
}
signed main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];b[i]=a[i]-a[i-1];} for(int i=1;i<=n;i++){for(int j=i;j<=n;j+=lowbit(j)){t[j]+=b[i];d[j]+=i*b[i];}}while(m--){int work,l,r,k;cin>>work;if(work==1){cin>>l>>r>>k;//原数组的区间修改->差分数组的两个单点修改->树状数组的修改for(int i=l;i<=n;i=i+lowbit(i)){t[i]+=k;//包含l的节点的值都要改d[i]+=l*k;}for(int i=r+1;i<=n;i=i+lowbit(i)){t[i]-=k;d[i]-=(r+1)*k;}}else{cin>>l>>r;cout<<get(r)-get(l-1)<<endl;//前缀和的使用}}return 0;
}

能给个赞嘛？求求了QAQ