树壮数组的拓展应用
首先看几个树壮数组的基本操作
一 求下一位
int lowbit(int x) { return x & -x; }
二 单点修改
void add(int k, int x, int y) {
while (x <= n) {
c[k][x] += y;
x += lowbit(x);
}
}
三 区间查询
ll ask(int k, int x) {
ll ans = 0;
while (x) {
ans += c[k][x];
x -= lowbit(x);
}
return ans;
}
树壮数组主要支持单点修改和前缀和查询。如果我们要查询区间[l,r]的信息,可以修改成查询r 的前缀 - (l-1)的前缀。如果要修改区间信息的话,我么可以使用线段树。当然树壮数组也是可以的,不过要变通一下。下面以一个具体的题目说明一下。
http://poj.org/problem?id=3468
A Simple Problem with Integers
Time Limit: 5000MS | Memory Limit: 131072K | |
Total Submissions: 146585 | Accepted: 45562 | |
Case Time Limit: 2000MS |
Description
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
Output
You need to answer all Q commands in order. One answer in a line.
Sample Input
10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4
Sample Output
4 55 9 15
Hint
The sums may exceed the range of 32-bit integers.
思路:对数组a进行操
1对于区间修改:
新建一个数组b,初始化全部为0,如果区间[l,r]的每个数都要加上x,那么我们可以对数组b进行操作, 即是单点操作b[l]+x,b[r+1]-x;这样之后我们单点查询a[i]的值得话就是a[i]+ask(i),(注意:这里的ask是对b数组进行查询)
2区间查询:
b数组的前缀和就是经过一系列的操作后a[x]增加的值。
那么序列a的前缀和a[1~x]整体增加的值就是:
可以改写为:
具体来说呢,我们可以建立两个数状数组c0,c1,初始化全部为0.对于每条指令“C l r d”,执行4个操作
①在树状数组c0中,把位置l上的数加上d;
②在树状数组c0中,把位置r+1上的数减去d;
③在树状数组c1中,把位置l上的数加上l*d;
④在树状数组c1中,把位置r+1上的数减去(r + 1)*d;
此外,我们建立sum存储序列a的原始前缀和。对于每条指令,“Q l r”,当然还是拆成1~r和1~l-1两个部分相减
(sum[r]+(r+1)*ask(c0,r)-ask(c1,r))- (sum[l-1]+l*ask(c0,l-1)-ask(c1,l-1));
代码如下:
/********************************************************************************
* @Author: PanLong
* @Style: ACM
* @Date: 2018-11-19
* @Description:
********************************************************************************/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define INF 1e18
using namespace std;
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 10;
int a[MAXN], n, m;
ll c[2][MAXN], sum[MAXN];
int lowbit(int x) { return x & -x; }
ll ask(int k, int x) {
ll ans = 0;
while (x) {
ans += c[k][x];
x -= lowbit(x);
}
return ans;
}
void add(int k, int x, int y) {
while (x <= n) {
c[k][x] += y;
x += lowbit(x);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
while (m--) {
char op[2]; int l, r, d;
scanf("%s%d%d",op,&l,&r);
if (op[0] == 'C') {
scanf("%d",&d);
add(0,l,d);
add(0,r+1,-d);
add(1,l,d*l);
add(1,r+1,-(r+1)*d);
}
else {
ll ans = sum[r] + (r + 1)*ask(0, r) - ask(1, r);
ans -= sum[l - 1] + l * ask(0, l-1) - ask(1,l-1);
printf("%lld\n",ans);
}
}
return 0;
}