树壮数组的拓展应用

首先看几个树壮数组的基本操作

一   求下一位

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

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