树状数组

前置知识

差分和前缀和

名称

树状数组的英文名是 Fenwick tree 或 BIT(Binary Indexed Tree)

Lowbit

lowbit(i)定义为能整除$i$的最大的$2$的次幂（$i$的约数中最大的$2$的次幂）。也可以理解为将$i$转为二进制之后最后一个$1$的权重。
lowbit(i)可以通过位运算i & -i很快的计算。
比如 lowbit(12) = 4 因为 12 的二进制是 1100
比如 lowbit(13) = 1 因为 13 的二进制是 1101

基本原理

设原数组为$\{a_i\} (1 \leq i \leq n)$定义新数组$c_i$，其中
$$c_i = \sum_{i - lowbit(i) < j \leq i} a_j$$
这样定义的优势，对于任意一个前缀，均可以用$O(\log n)$项拼出。
修改其中任意一项，都只需要修改$O(\log n)$个位置。

基本操作

修改单点

void change(int x, int y) {
    for (int i = x; i <= n; i += i & -i) {
        c[i] += y;
    }
}

查询前缀和

int query(int x) {
    int re = 0;
    for (int i = x; i > 0; i -= i & -i) {
        re += c[i];
    }
    return re;
}

$O(n)$初始化树状数组

和堆一样，如果希望$O(n)$构造一个树状数组，可以直接for循环。

根据数组a，初始化树状数组c，不需要$O(n \log n)$的时间，只需要 $O(n)$
Based on the intial array a[], construct the BIT c[], it need O(n) instead of O(n log n)

for (int i = 1; i <= n; i++)
{
    c[i] = a[i];
}
for (int i = 1; i <= n; i++)
{
    if (i + (i & -i) <= n)
    {
        c[i + (i & -i)] += c[i];
    }
}

第$k$大操作

c[1] = a[1]
c[2] = a[1] + a[2]
c[3] = a[3]
c[4] = a[1] + a[2] + a[3] + a[4]
c[5] = a[5]
c[6] = a[5] + a[6]
c[7] = a[7]
c[8] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8]

询问 x 希望找到 re 满足
a[1] + a[2] + a[3] + ... + a[re] < x
a[1] + a[2] + a[3] + ... + a[re] + a[re + 1] >= x

int ask(int x) {
    int re = 0;
    for (int i = 1 << 19; i > 0; i >>= 1) {
        if (re + i <= n && x > c[re + i]) {
            x -= c[re += i];
        }
    }
    return re + 1;
}

实现细节

1. 树状数组必须从1开始，不能从0开始

2. 修改操作只支持a[x] += y，如果需要a[x] = y需要额外维护数组a

3. 树状数组 支持的操作 一般是需要可逆

4. BIT must be used from 1, not zero, because lowbit(0) is 0

5. The update operation only supports increment not assignment.
   If assignment is needed, we need to maintain the initial array a[].

6. bisides addition, BIT supports other operators, such as xor (Exclusive OR).
   the operators generally need an inverse operator.

常见的可逆操作
Common inversible operators

1. + 加法 addition
2. + mod 加法取模 addition with mod
3. ^ 异或 （相当于，多维加法，每一维求和mod2） xor n-dimension of addition mod 2
4. * 前缀乘积（理论上可以，实际上没出现过）
   prefix product // multipilcation has an inverse operator, but it seldomly be used.

有一类特殊的动态规划，可以用树状数组维护前缀最大值

1. 修改，只会把a[x]越改越大（不会变小）
2. 询问只问前缀最大值（必须是前缀，不是任意区间）

这类题目有另一种方法：注意到单调性，用map来维护

For a special type of dynamic programming, we use BIT to maintain the maximum.

1. change, only change smaller a[x] to larger
2. query prefix only

Another solution: use map

树状数组，STL set与平衡树

许多平衡树的题目并不真的需要平衡树。

1. 如果可以离线，询问第$k$大，那么可以离线，离散化，树状数组。
2. 如果强制在线，不问第$k$大，只问前驱后继，那么可以STL set

其他推广

树状数组对于维护的信息要求比较苛刻，要求既可以加法，又可以加法。
所以常见的维护内容就是加法和异或。

在满足一定条件下（越改越大，只询问前缀）最大值的查询也可以用树状数组完成，这在一些DP题中有应用。

高维推广 / 二维树状数组

树状数组可以很容易的推广到高维的情况，单次操作时间复杂度为$O(\log^2 n)$从实际经验来看，基本只有二维和三维有利用价值。

c[i][j] = a[i - lowbit(i) + 1 .. i][j - lowbit(j) + 1 .. j] 共lowbit(i) * lowbit(j) 个数字
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]
a[i][j] = s[i][j] - s[i-1][j] - s[i][j-1] + s[i-1][j-1]
b[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]

2-D BIT

a[i][j]
c[i][j] = sum(a[i-lowbit(i)+1 .. i][j-lowbit(j)+1 .. j])
void change(int x, int y, int z)
{
    // a[x][y] += z;
    for (int i = x; i <= n; i += i & -i)
    {
        for (int j = y; j <= n; j += j & -j)
        {
            c[i][j] += z;
        }
    }
}

int query(int x, int y)
{
    int re = 0;
    for (int i = x; i > 0; i -= i & -i)
    {
        for (int j = y; j > 0; j -= j & -j)
        {
            re += a[i][j];
        }
    }
    return re;
}


3-D and 2-D are very similar
The more Demension, the higher the time complexity.

参考题目

poj 2352
二维偏序，排序一维，树状数组做一维。

poj 3468
可以使用线段树，也可以使用

poj 2155
二维树状数组，异或。

133. 二维树状数组 1：单点修改，区间查询

https://loj.ac/problem/133

c[i][j] = a[i - lowbit(i) + 1 .. i][j - lowbit(j) + 1 .. j]

134. 二维树状数组 2：区间修改，单点查询

https://loj.ac/problem/134

135. 二维树状数组 3：区间修改，区间查询

https://loj.ac/problem/135

https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
https://cp-algorithms.com/data_structures/fenwick.html

http://poj.org/problem?id=2155
http://poj.org/problem?id=2352
http://poj.org/problem?id=2828
http://poj.org/problem?id=3468
http://www.spoj.com/problems/INVCNT/

https://atcoder.jp/contests/abc185/tasks/abc185_f

Error: ENOENT: no such file or directory, open '/Users/wwwwodddd/Dropbox/Informatics/problems/P4514'

Error: ENOENT: no such file or directory, open '/Users/wwwwodddd/Dropbox/Informatics/problems/P3369'

P3960 [NOIP2017 提高组] 列队

https://www.luogu.com.cn/problem/P3960

题目背景

题目描述

Sylvia 是一个热爱学习的女孩子。

前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。

Sylvia 所在的方阵中有 $n \times m$ 名学生，方阵的行数为 $n$，列数为 $m$。

为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中 的学生从 $1$ 到 $n \times m$ 编上了号码（参见后面的样例）。即：初始时，第 $i$ 行第 $j$ 列 的学生的编号是 $(i-1)\times m + j$。

然而在练习方阵的时候，经常会有学生因为各种各样的事情需要离队。在一天 中，一共发生了 $q$ 件这样的离队事件。每一次离队事件可以用数对 $(x,y) (1 \le x \le n, 1 \le y \le m)$ 描述，表示第 $x$ 行第 $y$ 列的学生离队。

在有学生离队后，队伍中出现了一个空位。为了队伍的整齐，教官会依次下达 这样的两条指令：

1. 向左看齐。这时第一列保持不动，所有学生向左填补空缺。不难发现在这条 指令之后，空位在第 $x$ 行第 $m$ 列。

2. 向前看齐。这时第一行保持不动，所有学生向前填补空缺。不难发现在这条 指令之后，空位在第 $n$ 行第 $m$ 列。

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后， 下一个学生才能离队。因此在每一个离队的学生要归队时，队伍中有且仅有第 $n$ 行 第 $m$ 列一个空位，这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊，所以 Sylvia 想要计算每一次离队事件中，离队的同学 的编号是多少。

注意：每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后 方阵中同学的编号可能是乱序的。

输入格式

输入共 $q+1$ 行。

第一行包含 $3$ 个用空格分隔的正整数 $n, m, q$，表示方阵大小是 $n$ 行 $m$ 列，一共发 生了 $q$ 次事件。

接下来 $q$ 行按照事件发生顺序描述了 $q$ 件事件。每一行是两个整数 $x, y$，用一个空 格分隔，表示这个离队事件中离队的学生当时排在第 $x$ 行第 $y$ 列。

输出格式

按照事件输入的顺序，每一个事件输出一行一个整数，表示这个离队事件中离队学生的编号。

样例 #1

样例输入 #1

2 2 3 
1 1 
2 2 
1 2 

样例输出 #1

1
1
4

提示

【输入输出样例 $1$ 说明】

列队的过程如上图所示，每一行描述了一个事件。 在第一个事件中，编号为 $1$ 的同学离队，这时空位在第一行第一列。接着所有同学 向左标齐，这时编号为 $2$ 的同学向左移动一步，空位移动到第一行第二列。然后所有同 学向上标齐，这时编号为 $4$ 的同学向上一步，这时空位移动到第二行第二列。最后编号为 $1$ 的同学返回填补到空位中。

【数据规模与约定】

测试点编号	$n$	$m$	$q$	其他约定
$1\sim 6$	$\le 10^3$	$\le 10^3$	$\le 500$	无
$7\sim 10$	$\le 5\times 10^4$	$\le 5\times 10^4$	$\le 500$	无
$11\sim 12$	$=1$	$\le 10^5$	$\le 10^5$	所有事件 $x=1$
$13\sim 14$	$=1$	$\le 3\times 10^5$	$\le 3\times 10^5$	所有事件 $x=1$
$15\sim 16$	$\le 3\times 10^5$	$\le 3\times 10^5$	$\le 3\times 10^5$	所有事件 $x=1$
$17\sim 18$	$\le 10^5$	$\le 10^5$	$\le 10^5$	无
$19\sim 20$	$\le 3\times 10^5$	$\le 3\times 10^5$	$\le 3\times 10^5$	无

数据保证每一个事件满足 $1 \le x \le n,1 \le y \le m$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, q, x[300020], y[300020], N;
long long z[300020];
int c[600020];
vector<pair<int, int> > a[300020];
vector<long long> b[300020], l;
void R(int x, int y) {
	for (; x <= N; x += x & -x) {
		c[x] += y;
	}
}
int A(int x) {
	int re = 0;
	for (int i = 1 << 20; i > 0; i /= 2) {
		if (re + i <= N && c[re + i] < x) {
			x -= c[re += i];
		}
	}
	return re + 1;
}
int main() {
	scanf("%d%d%d", &n, &m, &q);
	N = max(n, m) + q;
	for (int i = 0; i < q; i++) {
		scanf("%d%d", &x[i], &y[i]);
		if (y[i] < m) {
			a[x[i]].push_back(make_pair(y[i], i));
		}
	}
	for (int i = 1; i <= N; i++) {
		c[i]++;
		if (i + (i & -i) <= N) {
			c[i + (i & - i)] += c[i];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < a[i].size(); j++) {
			int u = A(a[i][j].first);
			z[a[i][j].second] = u;
			R(u, -1);
		}
		for (int j = 0; j < a[i].size(); j++) {
			R(z[a[i][j].second], 1);
		}
	}
	for (int i = 0; i <= n; i++) {
		l.push_back((long long)i * m);
	}
	for (int i = 0; i < q; i++) {
		int u = A(x[i]);
		R(u, -1);
		if (y[i] < m) {
			b[x[i]].push_back(l[u]);
			if (z[i] < m) {
				z[i] = (long long)(x[i] - 1) * m + z[i];
			} else {
				z[i] = b[x[i]][z[i] - m];
			}
		} else {
			z[i] = l[u];
		}
		l.push_back(z[i]);
	}
	for (int i = 0; i < q; i++) {
		printf("%lld\n", z[i]);
	}
	return 0;
}

题解

这个题目需要询问第$k$个$1$的位置，所以可以树状数组。

P3374 【模板】树状数组 1

https://www.luogu.com.cn/problem/P3374

题目背景

题目描述

如题，已知一个数列，你需要进行下面两种操作：

• 将某一个数加上 $x$

• 求出某区间每一个数的和

输入格式

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

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

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

• 1 x k 含义：将第 $x$ 个数加上 $k$

• 2 x y 含义：输出区间 $[x,y]$ 内每个数的和

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

14
16

提示

【数据范围】

对于 $30\%$ 的数据，$1 \le n \le 8$，$1\le m \le 10$；
对于 $70\%$ 的数据，$1\le n,m \le 10^4$；
对于 $100\%$ 的数据，$1\le n,m \le 5\times 10^5$。

样例说明：

故输出结果14、16

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int c[500020];
void change(int x, int y) {
	for (int i = x; i <= n; i += i & -i) {
		c[i] += y;
	}
}
int query(int x) {
	int re = 0;
	for (int i = x; i > 0; i -= i & -i) {
		re += c[i];
	}
	return re;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		change(i, x);
	}
	for (int i = 0; i < m; i++) {
		int o, x, y;
		scanf("%d%d%d", &o, &x, &y);
		if (o == 1) {
			change(x, y);
		} else {
			printf("%d\n", query(y) - query(x - 1));
		}
	}
	return 0;
}

题解

区间和等于前缀和相减
a[l] + a[l+1] + a[l+2] + ... + a[r-1] + a[r] == query(r) - query(l-1)

P3368 【模板】树状数组 2

https://www.luogu.com.cn/problem/P3368

题目背景

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 $x$；

2. 求出某一个数的值。

输入格式

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

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

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

操作 $1$： 格式：1 x y k 含义：将区间 $[x,y]$ 内每个数加上 $k$；

操作 $2$： 格式：2 x 含义：输出第 $x$ 个数的值。

输出格式

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

样例 #1

样例输入 #1

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4

样例输出 #1

6
10

提示

样例 1 解释：

故输出结果为 6、10。

---

数据规模与约定

对于 $30\%$ 的数据：$N\le8$，$M\le10$；

对于 $70\%$ 的数据：$N\le 10000$，$M\le10000$；

对于 $100\%$ 的数据：$1 \leq N, M\le 500000$，$1 \leq x, y \leq n$，保证任意时刻序列中任意元素的绝对值都不大于 $2^{30}$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int c[500020];
int a[500020];
void change(int x, int y) {
	for (int i = x; i <= n; i += i & -i) {
		c[i] += y;
	}
}
int query(int x) {
	int re = 0;
	for (int i = x; i > 0; i -= i & -i) {
		re += c[i];
	}
	return re;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < m; i++) {
		int o, x, y, k;
		scanf("%d", &o);
		if (o == 1) {
			scanf("%d%d%d", &x, &y, &k);
			change(x, k);
			change(y + 1, -k);
		} else {
			scanf("%d", &x);
			printf("%d\n", query(x) + a[x]);
		}
	}
	return 0;
}

题解

0 1 5 4 2 3
0 1 4 -1 -2 1
操作 1 2 4 2
0 1 6 -1 -2 -1
操作 2 3，回答 1 6 -1

差分

a[1] a[2] a[3] ... a[n]

b[i] = a[i] - a[i-1]
a[i] = b[1] + b[2] + ... + b[i]

a[l-1] a[l] a[l+1] ... a[r-1] a[r] a[r+1]
b[l] = a[l] - a[l-1]
b[r+1] = a[r+1] - a[r]

a[l-1] a[l]+x a[l+1]+x ... a[r-1]+x a[r]+x a[r+1]
b[l] = a[l]+x - a[l-1]
b[r+1] = a[r+1] - a[r]-x

相当于修改b中的2个点，询问b的前缀和

初始全是 0
0 0 0 0 0 0

第3到第5个数字+=2
0 0 2 2 2 0

对于
0 0 2 2 2 0
求差分可以得到
0 0 2 0 0 -2

在差分上只改了2个位置
第3个位置+=2
第6个位置-=2

对于
0 0 2 0 0 -2
求前缀和可以得到
0 0 2 2 2 0

第2到第4个数字+=3
0 3 5 5 2 0
差分是
0 3 2 0 -3 -2

在差分上只改了2个位置
第2个位置+=3
第5个位置-=3

差分
b[i] = a[i] - a[i-1]

a[i] = b[1] + b[2] + b[3] + ... + b[i]

a数组中修改一个区间，b数组中只改变了2个位置
a: 0 0 0 x x x x 0 0 0 0
b: 0 0 0 +x 0 0 0 -x 0 0 0
index l i r r+1

a[i]

b[i] = a[i] - a[i-1]

a[x] += k, a[x+1] += k, ..., a[y]+=k
b[x] +=k, b[y+1] -= k
a[x] = b[1] + b[2] + ... + b[x]

P2068 统计和

https://www.luogu.com.cn/problem/P2068

题目背景

题目描述

给定一个长度为 $n(n\leq 100000)$，初始值都为 $0$ 的序列，$x(x\leq 100000)$ 次的修改某些位置上的数字，每次加上一个数，然后提出 $y(y\leq 100000)$ 个问题，求每段区间的和。

输入格式

第一行 $1$ 个整数，表示序列的长度 $n$。

第二行 $1$ 个整数，表示操作的次数 $w$。

后面依次是 $w$ 行，分别表示加入和询问操作。

其中，加入用 x 表示，询问用 y 表示。

$x$的格式为 x a b 表示在序列上第 $a$ 个数加上 $b$。保证 $1 \leq a \leq n$，$1 \leq b \leq 10^9$。

$y$ 的格式为 y a b 表示询问 $a$ 到 $b$ 区间的加和。保证 $1 \leq a \leq b \leq n$。

输出格式

每行一个正整数，分别是每次询问的结果

样例 #1

样例输入 #1

5
4
x 3 8
y 1 3
x 4 9
y 3 4

样例输出 #1

8
17

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
long long c[100020];
void change(int x, int y) {
	for (int i = x; i <= n; i += i & -i) {
		c[i] += y;
	}
}
long long query(int x) {
	long long re = 0;
	for (int i = x; i > 0; i -= i & -i) {
		re += c[i];
	}
	return re;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		char o;
		int x, y;
		scanf(" %c%d%d", &o, &x, &y);
		if (o == 'x') {
			change(x, y);
		} else {
			printf("%lld\n", query(y) - query(x - 1));
		}
	}
	return 0;
}

题解

读入字符参考C++字符串

其他参考 P3374

P5057 [CQOI2006]简单题

https://www.luogu.com.cn/problem/P5057

题目背景

题目描述

有一个 n 个元素的数组，每个元素初始均为 0。有 m 条指令，要么让其中一段连续序列数字反转——0 变 1，1
变 0（操作 1），要么询问某个元素的值（操作 2）。
例如当 n = 20 时，10 条指令如下：

输入格式

第一行包含两个整数 n, m，表示数组的长度和指令的条数； 以下 m 行，每行的第一个数 t 表示操作的种类：

若 t = 1，则接下来有两个数 L, R，表示区间 [L, R] 的每个数均反转； 若 t = 2，则接下来只有一个数 i，表示询问的下标。

输出格式

每个操作 2 输出一行（非 0 即 1），表示每次操作 2 的回答。

样例 #1

样例输入 #1

20 10
1 1 10
2 6
2 12
1 5 12
2 6
2 15
1 6 16
1 11 17
2 12
2 6

样例输出 #1

1
0
0
0
1
1

提示

对于 50% 的数据，1 ≤ n ≤ $10^3$, 1 ≤ m ≤ $10^4$；
对于 100% 的数据，1 ≤ n ≤ $10^5$, 1 ≤ m ≤ 5 × $10^5$，保证 L ≤ R。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int c[100020];
void change(int x, int y) {
	for (int i = x; i <= n; i += i & -i) {
		c[i] ^= y;
	}
}
int query(int x) {
	int re = 0;
	for (int i = x; i > 0; i -= i & -i) {
		re ^= c[i];
	}
	return re;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		int o, x, y;
		scanf("%d", &o);
		if (o == 1) {
			scanf("%d%d", &x, &y);
			change(x, 1);
			change(y + 1, 1);
		} else {
			scanf("%d", &x);
			printf("%d\n", query(x));
		}
	}
	return 0;
}

题解

只要可逆操作，就可以用树状数组维护

异或的差分

b 是 a 的差分
b[i] = a[i] ^ a[i-1]

a 是 b 的前缀异或
a[x] = b[1] ^ b[2] ^ ... ^ b[x]

如果 a 的区间异或同一个数字 k
a[x] ^= k, a[x+1] ^= k, ..., a[y]^=k

相当于在 b 中修改两个端点
b[x] ^=k, b[y+1] ^= k

P5142 区间方差

https://www.luogu.com.cn/problem/P5142

题目背景

出题人并没有能力写有趣的题面……

题目描述

对于一个长度为 $n$ 的序列 $a_1,a_2,a_3\cdots a_n$，我们定义它的平均数 $a$ 为:

$$a=\frac{1}{n}\sum_{i=1}^{n}a_i$$

并定义它的方差 $d$ 为:

$$d=\frac{1}{n}\sum_{i=1}^{n}(a_i-a)^2$$

现在给定一个长度为 $n$ 的序列 $b_1,b_2\cdots b_n$。你需要支持两种操作。每种操作的格式为 c x y。

若 $c=1$，为修改操作，代表将 $b_x$ 赋值为 $y$。

若 $c=2$，为查询操作，代表查询 $b_x$ 到 $b_y$ 的方差。

为了避免浮点数误差，请以分数取模形式输出结果（对 1000000007（$10^9+7$）取模）。

输入格式

第一行两个整数 $n,m$，代表序列 $b$ 的长度为 $n$，有 $m$ 个操作。

第二行 $n$ 个整数 $b_i$，表示序列 $b$ 的初始值。

下面有 $m$ 行整数，每行格式为 c x y，含义如上文所示。保证所有操作合法。

输出格式

对于每个操作 2，输出一行。

样例 #1

样例输入 #1

4 8
0 0 0 0
1 1 1
1 2 2
1 3 3
1 4 4
2 1 1
2 1 2
2 1 3
2 1 4

样例输出 #1

0
250000002
666666672
250000003

提示

样例 1 解释

四次修改后，序列 $b$ 为：$\{1,2,3,4\}$。

区间 $[1,1]$ 的方差为 $0$。

区间 $[1,2]$ 的方差为 $\frac{1}{4}$ 。$4$ 的逆元为 $250000002$。

区间 $[1,3]$ 的方差为 $\frac{2}{3}$。$3$ 的逆元为 $333333336$，$2\times333333336\bmod M=666666672$。

数据规模与约定

• 对于 $50\%$ 的数据，$n\leq 1000$，$m\leq 1000$。
• 对于 $100\%$ 的数据，$1\leq n,m\leq 1\times 10^5$，$1\leq b_i\leq 1\times 10^9$，$1\leq x\leq n$。对于操作 1，$1\leq y\leq 1\times 10^9$。对于操作2，$x\leq y\leq n$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, p = 1000000007;
int a[100020];
int c1[100020];
int c2[100020];
void change(int *c, int x, int y) {
	for (int i = x; i <= n; i += i & -i) {
		c[i] += y;
		if (c[i] >= p) {
			c[i] -= p;
		}
	}
}
int query(int *c, int x) {
	int re = 0;
	for (int i = x; i > 0; i -= i & -i) {
		re += c[i];
		if (re >= p) {
			re -= p;
		}
	}
	return re;
}
int inv(int x) {
	if (x == 1) {
		return 1;
	}
	return (long long)(p - p / x) * inv(p % x) % p;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		change(c1, i, a[i]);
		int t2 = (long long)a[i] * a[i] % p;
		change(c2, i, t2);
	}
	for (int i = 0; i < m; i++) {
		int o, x, y;
		scanf("%d%d%d", &o, &x, &y);
		if (o == 1) {
			int t1 = -a[x];
			int t2 = -(long long)a[x] * a[x] % p;
			a[x] = y;
			t1 = (t1 + a[x]) % p;
			t2 = (t2 + (long long)a[x] * a[x]) % p;
			if (t1 < 0) {
				t1 += p;
			}
			if (t2 < 0) {
				t2 += p;
			}
			change(c1, x, t1);
			change(c2, x, t2);
		} else {
			int invlen = inv(y - x + 1);
			int t1 = query(c1, y) - query(c1, x - 1);
			int t2 = query(c2, y) - query(c2, x - 1);
			t1 = (long long)t1 * invlen % p;
			t2 = (long long)t2 * invlen % p;
			int ans = (t2 - (long long)t1 * t1) % p;
			if (ans < 0) {
				ans += p;
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}

题解

方差 = 平方的平均数 - 平均数的平方

$1$和$3$ 两个数字的方差是$1$
平均数是$2$
平方的平均数是$5$

注意这个题目的操作不是
a[x] += y
而是
a[x] = y

数组 a 的方差为
$$\frac{a[1]^2 + a[2]^2 + ... + a[n]^2}{n} - \left (\frac{a[1] + a[2] + ... + a[n]}{n} \right )^2$$

$1$和$3$的方差为
$\frac{1 + 9}{2} - \left (\frac{1 + 3}{2} \right )^2 = 1$

先删（改成0）再加

change(c1, x, -a[x]);
change(c2, x, -a[x]*a[x]);
a[x] = y;
change(c1, x, +a[x]);
change(c2, x, +a[x]*a[x]);

算出前后变化量一起修改

change(c1, x, y-a[x]);
change(c2, x, y*y-a[x]*a[x]);
a[x] = y

需要使用 乘法逆元

P3608 [USACO17JAN]Balanced Photo G

https://www.luogu.com.cn/problem/P3608

题目背景

题目描述

Farmer John is arranging his $N$ cows in a line to take a photo ($1 \leq N \leq 100,000$). The height of the $i$th cow in sequence is $h_i$, and the heights of all cows are distinct.

As with all photographs of his cows, FJ wants this one to come out looking as nice as possible. He decides that cow $i$ looks "unbalanced" if $L_i$ and $R_i$ differ by more than factor of 2, where $L_i$ and $R_i$ are the number of cows taller than $i$ on her left and right, respectively. That is, $i$ is unbalanced if the larger of $L_i$ and $R_i$ is strictly more than twice the smaller of these two numbers. FJ is hoping that not too many of his cows are unbalanced.

Please help FJ compute the total number of unbalanced cows.

FJ正在安排他的N头奶牛站成一排来拍照。（1<=N<=100,000)序列中的第i头奶牛的高度是h[i]，且序列中所有的奶牛的身高都不同。

就像他的所有牛的照片一样，FJ希望这张照片看上去尽可能好。他认为，如果L[i]和R[i]的数目相差1倍以上，第i头奶牛就是不平衡的（L[i]和R[i]分别代表第i头奶牛左右两边比她高的奶牛的数量）。也就是说，如果L[i]和R[i]中的较大数大于较小数的两倍，第i头奶牛就是不平衡的。FJ不希望他有太多的奶牛不平衡。

请帮助FJ计算不平衡的奶牛数量。

输入格式

The first line of input contains $N$. The next $N$ lines contain $h_1 \ldots h_N$, each a nonnegative integer at most 1,000,000,000.

第一行一个整数N。接下N行包括H[1]到H[n]，每行一个非负整数（不大于1,000，000，000)。

输出格式

Please output a count of the number of cows that are unbalanced.

请输出不平衡的奶牛数量。

样例 #1

样例输入 #1

7
34
6
23
0
5
99
2

样例输出 #1

3

提示

感谢 @XY星系质量PK 的翻译

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, z;
int h[100020];
int o[100020];
int c[100020];
void change(int x, int y)
{
	for (; x <= n; x += x & -x)
	{
		c[x] += y;
	}
}
int query(int x)
{
	int re = 0;
	for (; x > 0; x -= x & -x)
	{
		re += c[x];
	}
	return re;
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &h[i]);
		o[i] = i;
	}
	sort(o + 1, o + 1 + n, [](int x,int y){return h[x]>h[y];});
	for (int i = 1; i <= n; i++)
	{
		int l = query(o[i]);
		int r = i - 1 - l;
		if (max(l, r) > 2 * min(l, r))
		{
			z++;
		}
		change(o[i], 1);
	}
	printf("%d\n", z);
	return 0;
}

题解

http://usaco.org/index.php?page=viewproblem2&cpid=693

本题可以离散化离散化

将所有奶牛
sort(o+1,o+1+n,[](int x,int y){return h[x]>h[y];});
o 排名数组
把o按照h降序排序（因为最后是h[x]>h[y]
排序之后
h[o[1]] 是 h数组中最大的数字
h[o[2]] 是 h数组中次大的数字
...
h[o[n]] 是 h数组中最小的数字

// for each i, count how many j, j < i && a[j] > a[i]
// for each i, count how many j, j > i && a[j] < a[i]

sort (value, position) in inceasing order

for (int i = 0; i < n; i++)
{
ans += i - query(a[i].position);
// the number of j (a[j].value < a[i].value && a[j].position > a[i].position) after a[i].position;
change(a[i].position, 1);
}

排序
(高度，位置)
从高到低依次处理所有奶牛
a[i].fisrt 高度
a[i].second 位置
for (int i = n-1; i >= 0; i++)
{
// 在自己之前加入的，一定比自己高
int L = query(a[i].second); // 位置在自己的左边
int R = n - 1 - i - L; // 位置在自己的右边
// 不需要询问query(n)，因为答案一定是n-1-i
change(a[i].second, 1);
if (max(L, R) > 2 * min(L,R))
{
ans++;
}
}

inversion

i < j && a[i] < a[j] && b[i] < b[j]

非常直接的思路：
高度离散化到1到n
从左向右做一次，可以得到每个数字左边有几个比自己大的
从右向左做一次，可以得到每个数字右边有几个比自己大的

把所有牛按照高度排序(高度, 下标)，从高到底
枚举所有的牛，
询问 当前牛左边的和是多少 当前牛右边的和是多少 计算是否平衡
当前牛的位置 += 1

逆序对的个数，等价于冒泡排序，需要的交换次数（只能交换相邻2个）

两类做法：

1. 归并排序
2. （离散化/排序）树状数组

非常直接的思路：
直接离散化a数组

按照(a[i], i)排序
扫描所有的(a[i], i)

2 8 0 3
生成
(2, 1)
(8, 2)
(0, 3)
(3, 4)

排序
(0, 3)
(2, 1)
(3, 4)
(8, 2)

答案 += (>i的所有位置之和是多少) = (全部的和 - <=i的位置之和)
位置i += 1

010001
010011
010111
011111
111111

P6278 [USACO20OPEN]Haircut G

https://www.luogu.com.cn/problem/P6278

题目背景

题目描述

Farmer John 由于对整理他难以整平的头发感到疲惫，于是决定去理发。他有一排 $N$ 缕头发，第 $i$ 缕头发初始时长度为 $A_i$ 微米（$0\le A_i\le N$）。理想情况下，他想要他的头发在长度上单调递增，所以他定义他的头发的“不良度”为逆序对的数量：满足 $i < j$ 及 $A_i > A_j$ 的二元对 $(i,j)$。
对于每一个 $j=0,1,\ldots,N-1$，Farmer John 想要知道他所有长度大于 $j$ 的头发的长度均减少到 $j$ 时他的头发的不良度。

---

（有趣的事实：人类平均确实有大约 $10^5$ 根头发！）

输入格式

输入的第一行包含 $N$。
第二行包含 $A_1,A_2,\ldots,A_N$。

输出格式

对于每一个 $j=0,1,\ldots,N-1$，用一行输出 Farmer John 头发的不良度。

---

注意这个问题涉及到的整数大小可能需要使用 $64$ 位整数型存储（例如，C/C++ 中的“long long”）。

样例 #1

样例输入 #1

5
5 2 3 3 0

样例输出 #1

0
4
4
5
7

提示

样例解释：

输出的第四行描述了 Farmer John 的头发长度减少到 $3$ 时的逆序对数量。
$A=[3,2,3,3,0]$ 有五个逆序对：$A_1>A_2,\,A_1>A_5,\,A_2>A_5,\,A_3>A_5,$ 和 $A_4>A_5$。

---

对于 $100\%$ 的数据，$1\le N\le 10^5$。

共 $13$ 个测试点，其中 $1$ 为样例，其余性质如下：

测试点 $2$ 满足 $N\le 100$。
测试点 $3\sim 5$ 满足 $N\le 5000$。
测试点 $6\sim 13$ 没有额外限制。

---

出题人：Dhruv Rohatgi

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int c[100020];
void change(int x, int y)
{
	for (x++; x <= n + 1; x += x & -x)
	{
		c[x] += y;
	}
}
int query(int x)
{
	int re = 0;
	for (x++; x > 0; x -= x & -x)
	{
		re += c[x];
	}
	return re;
}
long long z[100020];
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		int u = i - query(x);
		z[x] += u;
		change(x, 1);
	}
	long long s = 0;
	for (int i = 0; i < n; i++)
	{
		printf("%lld\n", s);
		s += z[i];
	}
	return 0;
}

题解

http://usaco.org/index.php?page=viewproblem2&cpid=1041

5
5 2 3 3 0

0 1 1 1 4

如果j>5那么答案+=0
如果j>2那么答案+=1
如果j>3那么答案+=1
如果j>3那么答案+=1
如果j>0那么答案+=4

For each i
how many j j < i && a[j] > a[i]

contribution the number of inversion, (j, i)

If decrease to something x
if x > a[i] then the contribution of i does not change
cnt[a[i]] += the number of j (j < i && a[j] > a[i])

if x <= a[i] then the contribution of i is 0

Get the answer of x,
sum cnt[1] + cnt[2] + .. + cnt[x-1]

P6278 [USACO20OPEN]Haircut G

5 2 3 3 0
计算每个位置之前有几个比自己大的
0 1 1 1 4
如果和j取min，相当于
所有a[i]>=j的位置贡献变成0
所有a[i]<j的位置贡献不变

ans[n] = 7
ans[n-1] = ans[n] - (a[???] == n-1的位置的贡献)
...
ans[0]

也可以正序解决
ans[0] = 0
ans[1] = ans[0] + (a[???] == 0的贡献)

ans[i] = ans[i-1] + (a[???] == i-1的贡献)

另一种想法
把所有
(a[i], a[i]带来的贡献排序)

P5200 [USACO19JAN]Sleepy Cow Sorting G

https://www.luogu.com.cn/problem/P5200

题目背景

目前征集本题SPJ

USACO 19年一月月赛金组第二题

题目描述

Farmer John正在尝试将他的 $N$ 头奶牛（$1\le N\le 10^5$），方便起见编号为 $1\ldots N$，在她们前往牧草地吃早餐之前排好顺序。

当前，这些奶牛以 $p_1,p_2,p_3,\ldots,p_N$ 的顺序排成一行，Farmer John站在奶牛 $p_1$ 前面。他想要重新排列这些奶牛，使得她们的顺序变为 $1,2,3,\ldots,N$，奶牛 $1$ 在 Farmer John 旁边。

今天奶牛们有些困倦，所以任何时刻都只有直接面向 Farmer John 的奶牛会注意听 Farmer John 的指令。每一次他可以命令这头奶牛沿着队伍向后移动 $k$ 步，$k$ 可以是 $1$ 到 $N-1$ 之间的任意数。她经过的 $k$ 头奶牛会向前移动，腾出空间使得她能够插入到队伍中这些奶牛之后的位置。

例如，假设 $N=4$，奶牛们开始时是这样的顺序：

 FJ: 4 3 2 1

唯一注意 FJ 指令的奶牛是奶牛 $4$。当他命令她向队伍后移动 $2$ 步之后，队伍的顺序会变成：

 FJ: 3 2 4 1 

现在唯一注意 FJ 指令的奶牛是奶牛 $3$，所以第二次他可以给奶牛 $3$ 下命令，如此进行直到奶牛们排好了顺序。

Farmer John 急欲完成排序，这样他就可以回到他的农舍里享用他自己的早餐了。请帮助他求出一个操作序列，使得能够用最少的操作次数将奶牛们排好顺序。

输入格式

输入的第一行包含 $N$。第二行包含 $N$ 个空格分隔的整数：$p_1,p_2,p_3,\ldots,p_N$，表示奶牛们的起始顺序。

输出格式

输出的第一行包含一个整数 $K$，为将奶牛们排好顺序所需的最小操作次数。

第二行包含 $K$ 个空格分隔的整数，$c_1,c_2,\ldots,c_K$，每个数均在 $1\ldots N-1$ 之间。如果第 $i$ 次操作 FJ 命令面向他的奶牛向队伍后移动 $c_i$ 步，那么 $K$ 次操作过后奶牛们应该排好了顺序。

如果存在多种最优的操作序列，你的程序可以输出其中任何一种。

样例 #1

样例输入 #1

4
1 2 4 3

样例输出 #1

3
2 2 3

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int c[1000020];
int a[1000020];
int z[1000020];
int v[1000020];
void change(int x, int y) {
	for (int i = x; i <= n; i += i & -i) {
		c[i] += y;
	}
}
int query(int x) {
	int re = 0;
	for (int i = x; i > 0; i -= i & -i) {
		re += c[i];
	}
	return re;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		change(a[i], 1);
	}
	int ans = -1;
	for (int i = n - 1; i >= 0; i--) {
		if (i == 0 || a[i - 1] > a[i]) {
			ans = i;
			break;
		}
	}
	printf("%d\n", ans);
	for (int i = ans - 1; i >= 0; i--) {
		change(a[i], -1);
		z[i] = query(a[i]) + ans - 1 - i;
	}
	if (ans == 0) {
		printf("\n");
	} else {
		for (int i = 0; i < ans; i++) {
			printf("%d%c", z[i], i == ans - 1 ? '\n' : ' ');
		}
	}
	return 0;
}

题解

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

问最少发出几个命令
发出的命令是什么

注意到没有接收到命令的奶牛（最后若干个奶牛），相对位置不会改变，所以初始必须是有序的

第一问 = n - 最大的升序的长度
the minimum number of time steps = n - the longest sorted suffix

在线
输入一个询问，回答一个询问
往往预处理相关

离线
先读入所有询问，排序……分组……处理这些询问
最后一起回答

如果一个题目在线可以做，离线一定可以做
有的题目在线的做法比离线的做法麻烦非常多
有一些题目强制在线

有的题目离线的做法比在线的做法简单很多

树状数组：
常见错误

1. 必须从1开始
2. 修改中的上界，是多少，要考虑清楚

P3660 [USACO17FEB]Why Did the Cow Cross the Road III G

https://www.luogu.com.cn/problem/P3660

题目背景

给定长度为2N的序列，1~N各处现过2次，i第一次出现位置记为ai，第二次记为bi，求满足ai<aj<bi<bj的对数

题目描述

The layout of Farmer John's farm is quite peculiar, with a large circular road running around the perimeter of the main field on which his cows graze during the day. Every morning, the cows cross this road on their way towards the field, and every evening they all cross again as they leave the field and return to the barn.

As we know, cows are creatures of habit, and they each cross the road the same way every day. Each cow crosses into the field at a different point from where she crosses out of the field, and all of these crossing points are distinct from each-other. Farmer John owns $N$ cows, conveniently identified with the integer IDs $1 \ldots N$, so there are precisely $2N$ crossing points around the road. Farmer John records these crossing points concisely by scanning around the circle clockwise, writing down the ID of the cow for each crossing point, ultimately forming a sequence with $2N$ numbers in which each number appears exactly twice. He does not record which crossing points are entry points and which are exit points.

Looking at his map of crossing points, Farmer John is curious how many times various pairs of cows might cross paths during the day. He calls a pair of cows $(a,b)$ a "crossing" pair if cow $a$'s path from entry to exit must cross cow $b$'s path from entry to exit. Please help Farmer John count the total number of crossing pairs.

输入格式

The first line of input contains $N$ ($1 \leq N \leq 50,000$), and the next $2N$ lines describe the cow IDs for the sequence of entry and exit points around the field.

输出格式

Please print the total number of crossing pairs.

样例 #1

样例输入 #1

4
3
2
4
4
1
3
2
1

样例输出 #1

3

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, x, z;
int c[100020];
pair<int, int> a[50020];
void R(int x, int y)
{
	for (; x <= 2 * n; x += x & -x)
	{
		c[x] += y;
	}
}
int G(int x)
{
	int re = 0;
	for (; x > 0; x -= x & -x)
	{
		re += c[x];
	}
	return re;
}
int main()
{
	cin >> n;
	for (int i = 1; i <= 2 * n; i++)
	{
		cin >> x;
		a[x].first = a[x].second;
		a[x].second = i;
	}
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++)
	{
		z += G(a[i].second) - G(a[i].first);
		R(a[i].second, 1);
	}
	cout << z << endl;
	return 0;
}

题解

http://usaco.org/index.php?page=viewproblem2&cpid=719

1 ... 2 ... 1 ... 2
sort the intervals, BIT
a[1] = (5, 8)
a[2] = (2, 7)
a[3] = (1, 6)
a[4] = (3, 4)

solution 1:
sort them by the length of interval, decreasing order

for (int i = 0; i < n; i++)
{
ans += query(a[i].right) - query(a[i].left);
change(a[i].left, 1);
change(a[i].right, 1);
}

a[3] = (1, 6)
a[2] = (2, 7)
a[1] = (5, 8)
a[4] = (3, 4)

ans = 0
[0 0 0 0 0 0]0 0 ans += 0
1[0 0 0 0 1 0]0 ans += 1
1 1 0 0[0 1 1 0]ans += 2
1 1[0 0]1 1 1 1 ans += 0
1 1 1 1 1 1 1 1 ans == 3

solution 2:
sort them by the left point

for (int i = 0; i < n; i++)
{
ans += query(a[i].right) - query(a[i].left);
change(a[i].right, 1);
}

a[3] = (1, 6)
a[2] = (2, 7)
a[4] = (3, 4)
a[1] = (5, 8)

ans = 0
[0 0 0 0 0 0]0 0 ans += 0
0[0 0 0 0 1 0]0 ans += 1
0 0[0 0]0 1 0 0 ans += 0
0 0 0 1[0 1 1 0]ans += 2
0 0 0 1 0 1 1 1 ans == 3

生成所有的区间，排序，用树状数组维护部分和

a[i] = make_pair(i第一次出现的位置, i第二次出现的位置)
把i排序

做法一：
1.
按照区间长度，从大到小排序
扫描所有区间
将区间内的和加入答案
将区间的2个端点+=1

把 所有区间 排序，区间长的在前，区间短的在后
bool cmp(pair<int, int> a, pair<int, int> b)
{
return a.second - a.first > b.second - b.first;
}

for (int i = 0; i < n; i++)
{
ans += query(a[i].second) - query(a[i].first);
change(a[i].first, 1);
change(a[i].second, 1);
}

因为先做的是比较长的区间，所以统计答案时不会有包含的情况

做法二：

按照区间左端点排序
扫描所有区间
将区间内的和加入答案
将右端点+=1

区间排序，先排左端点，再排右端点
for (int i = 0; i < n; i++)
{
ans += query(a[i].second) - query(a[i].first);
change(a[i].second, 1);
}

P3372 【模板】线段树 1

https://www.luogu.com.cn/problem/P3372

题目背景

题目描述

如题，已知一个数列，你需要进行下面两种操作：

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

输入格式

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

第二行包含 $n$ 个用空格分隔的整数，其中第 $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

提示

对于 $30\%$ 的数据：$n \le 8$，$m \le 10$。
对于 $70\%$ 的数据：$n \le {10}^3$，$m \le {10}^4$。
对于 $100\%$ 的数据：$1 \le n, m \le {10}^5$。

保证任意时刻数列中任意元素的和在 $[-2^{63}, 2^{63})$ 内。

【样例解释】

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
long long a[100020];
long long sm[400020];
long long ad[400020];
void build(int x, int l, int r) {
	if (l == r) {
		sm[x] = a[l];
		return;
	}
	int mid = (l + r) / 2;
	build(x * 2, l, mid);
	build(x * 2 + 1, mid + 1, r);
	sm[x] = sm[x * 2] + sm[x * 2 + 1];
}
void add(int x, int l, int r, long long v) {
	sm[x] += (r - l + 1) * v;
	ad[x] += v;
}
void push(int x, int l, int r) {
	int mid = (l + r) / 2;
	add(x * 2, l, mid, ad[x]);
	add(x * 2 + 1, mid + 1, r, ad[x]);
	ad[x] = 0;
}
void change(int x, int l, int r, int L, int R, long long v) {
	if (r < L || R < l) {
		return;
	}
	if (L <= l && r <= R) {
		add(x, l, r, v);
		return;
	}
	push(x, l, r);
	int mid = (l + r) / 2;
	change(x * 2, l, mid, L, R, v);
	change(x * 2 + 1, mid + 1, r, L, R, v);
	sm[x] = sm[x * 2] + sm[x * 2 + 1];
}
long long query(int x, int l, int r, int L, int R) {
	if (r < L || R < l) {
		return 0;
	}
	if (L <= l && r <= R) {
		return sm[x];
	}
	push(x, l, r);
	int mid = (l + r) / 2;
	return query(x * 2, l, mid, L, R) + query(x * 2 + 1, mid + 1, r, L, R);
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	build(1, 1, n);
	for (int i = 0; i < m; i++) {
		int o, x, y;
		long long z;
		scanf("%d", &o);
		if (o == 1) {
			scanf("%d%d%lld", &x, &y, &z);
			change(1, 1, n, x, y, z);
		} else {
			scanf("%d%d", &x, &y);
			printf("%lld\n", query(1, 1, n, x, y));
		}
	}
	return 0;
}

题解

https://www.luogu.com.cn/problem/P3372
http://poj.org/problem?id=3468

1. 修改单点，区间询问
2. 修改区间，单点询问
3. 修改区间，区间询问

差分
b[i] = a[i] - a[i-1]

a[i] = b[1] + b[2] + b[3] + ... + b[i]

询问 a[1] + a[2] + a[3] + ... + a[i]
询问 b[1] * i + b[2] * (i-1) + b[3] * (i-2) + ... + b[i] * 1
询问 (i+1) * (b[1] + b[2] + ... + b[i]) - (b[1] * 1 + b[2] * 2 + ... + b[i] * i)

分别维护 b[i] 和 b[i] * i 的前缀和

P4868 Preprefix sum

https://www.luogu.com.cn/problem/P4868

题目背景

题目描述

前缀和(prefix sum)$S_i=\sum_{k=1}^i a_k$。

前前缀和(preprefix sum) 则把$S_i$作为原序列再进行前缀和。记再次求得前缀和第i个是$SS_i$

给一个长度n的序列$a_1, a_2, \cdots, a_n$，有两种操作：

1. Modify i x：把$a_i$改成$x$；
2. Query i：查询$SS_i$

输入格式

第一行给出两个整数N，M。分别表示序列长度和操作个数
接下来一行有N个数，即给定的序列a1,a2,....an
接下来M行，每行对应一个操作，格式见题目描述

输出格式

对于每个询问操作，输出一行，表示所询问的SSi的值。

样例 #1

样例输入 #1

5 3
1 2 3 4 5
Query 5
Modify 3 2
Query 5

样例输出 #1

35
32

提示

1<=N,M<=100000,且在任意时刻0<=Ai<=100000

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
long long a[100020];
long long b[100020];
long long sm[400020];
long long ad[400020];
void build(int x, int l, int r) {
	if (l == r) {
		sm[x] = b[l];
		return;
	}
	int mid = (l + r) / 2;
	build(x * 2, l, mid);
	build(x * 2 + 1, mid + 1, r);
	sm[x] = sm[x * 2] + sm[x * 2 + 1];
}
void add(int x, int l, int r, long long v) {
	sm[x] += (r - l + 1) * v;
	ad[x] += v;
}
void push(int x, int l, int r) {
	int mid = (l + r) / 2;
	add(x * 2, l, mid, ad[x]);
	add(x * 2 + 1, mid + 1, r, ad[x]);
	ad[x] = 0;
}
void change(int x, int l, int r, int L, int R, long long v) {
	if (r < L || R < l) {
		return;
	}
	if (L <= l && r <= R) {
		add(x, l, r, v);
		return;
	}
	push(x, l, r);
	int mid = (l + r) / 2;
	change(x * 2, l, mid, L, R, v);
	change(x * 2 + 1, mid + 1, r, L, R, v);
	sm[x] = sm[x * 2] + sm[x * 2 + 1];
}
long long query(int x, int l, int r, int L, int R) {
	if (r < L || R < l) {
		return 0;
	}
	if (L <= l && r <= R) {
		return sm[x];
	}
	push(x, l, r);
	int mid = (l + r) / 2;
	return query(x * 2, l, mid, L, R) + query(x * 2 + 1, mid + 1, r, L, R);
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		b[i] = b[i - 1] + a[i];
	}
	build(1, 1, n);
	for (int i = 0; i < m; i++) {
		char o[9];
		int x, y;
		scanf("%s", o);
		if (*o == 'M') {
			scanf("%d%d", &x, &y);
			change(1, 1, n, x, n, y - a[x]);
			a[x] = y;
		} else {
			scanf("%d", &x);
			printf("%lld\n", query(1, 1, n, 1, x));
		}
	}
	return 0;
}

题解

https://www.luogu.com.cn/problem/P4868

偷懒的做法就是直接贴 线段树1 的代码
和 线段树 1 类似

SS[i] = S[1] + S[2] + ... + S[i]
S[i] = a[1] + a[2] + ... + a[i]
SS[i] = i * a[1] + (i-1) * a[2] + ... + 1 * a[i]
SS[i] = (i + 1) * (a[1] + a[2] + ... + a[i]) - (1 * a[1] + 2 * a[2] + ... + i * a[i])

用两个树状数组，维护 a[i] 和 i*a[i] 的前缀和

P3605 [USACO17JAN]Promotion Counting P

https://www.luogu.com.cn/problem/P3605

题目背景

题目描述

The cows have once again tried to form a startup company, failing to remember from past experience that cows make terrible managers!

The cows, conveniently numbered $1 \ldots N$ ($1 \leq N \leq 100,000$), organize the company as a tree, with cow 1 as the president (the root of the tree). Each cow except the president has a single manager (its "parent" in the tree). Each cow $i$ has a distinct proficiency rating, $p(i)$, which describes how good she is at her job. If cow $i$ is an ancestor (e.g., a manager of a manager of a manager) of cow $j$, then we say $j$ is a subordinate of $i$.

Unfortunately, the cows find that it is often the case that a manager has less proficiency than several of her subordinates, in which case the manager should consider promoting some of her subordinates. Your task is to help the cows figure out when this is happening. For each cow $i$ in the company, please count the number of subordinates $j$ where $p(j) > p(i)$.

奶牛们又一次试图创建一家创业公司，还是没有从过去的经验中吸取教训--牛是可怕的管理者！

为了方便，把奶牛从 $1\sim n$ 编号，把公司组织成一棵树，1 号奶牛作为总裁（这棵树的根节点）。除了总裁以外的每头奶牛都有一个单独的上司（它在树上的 “双亲结点”）。

所有的第 $i$ 头牛都有一个不同的能力指数 $p_i$，描述了她对其工作的擅长程度。如果奶牛 $i$ 是奶牛 $j$ 的祖先节点，那么我们我们把奶牛 $j$ 叫做 $i$ 的下属。

不幸地是，奶牛们发现经常发生一个上司比她的一些下属能力低的情况，在这种情况下，上司应当考虑晋升她的一些下属。你的任务是帮助奶牛弄清楚这是什么时候发生的。简而言之，对于公司的中的每一头奶牛 $i$，请计算其下属 $j$ 的数量满足 $p_j > p_i$。

输入格式

The first line of input contains $N$.

The next $N$ lines of input contain the proficiency ratings $p(1) \ldots p(N)$ for the cows. Each is a distinct integer in the range $1 \ldots 1,000,000,000$.

The next $N-1$ lines describe the manager (parent) for cows $2 \ldots N$. Recall that cow 1 has no manager, being the president.

输入的第一行包括一个整数 $n$。

接下来的 $n$ 行包括奶牛们的能力指数 $p_1,p_2 \dots p_n$。保证所有数互不相同。

接下来的 $n-1$ 行描述了奶牛 $2 \sim n$ 的上司的编号。再次提醒，1 号奶牛作为总裁，没有上司。

输出格式

Please print $N$ lines of output. The $i$th line of output should tell the number of subordinates of cow $i$ with higher proficiency than cow $i$.

输出包括 $n$ 行。输出的第 $i$ 行应当给出有多少奶牛 $i$ 的下属比奶牛 $i$ 能力高。

样例 #1

样例输入 #1

5
804289384
846930887
681692778
714636916
957747794
1
1
2
3

样例输出 #1

2
0
1
0
0

提示

感谢@rushcheyo 的翻译

【数据范围】
对于 $100\%$ 的数据，$1\le n \le 10^5$，$1 \le p_i \le 10^9$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, ss, x;
vector<int> a[100020];
int p[100020];
int o[100020];
int l[100020];
int r[100020];
int c[100020];
int z[100020];
void dfs(int x)
{
	l[x] = ss;
	for (int i: a[x])
	{
		dfs(i);
	}
	r[x] = ++ss;
}
void change(int x, int y)
{
	for (; x <= n; x += x & -x)
	{
		c[x] += y;
	}
}
int query(int x)
{
	int re = 0;
	for (; x > 0; x -= x & -x)
	{
		re += c[x];
	}
	return re;
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &p[i]);
		o[i] = i;
	}
	sort(o + 1, o + 1 + n, [](int x,int y){return p[x]>p[y];});
	for (int i = 2; i <= n; i++)
	{
		scanf("%d", &x);
		a[x].push_back(i);
	}
	dfs(1);
	for (int i = 1; i <= n; i++)
	{
		z[o[i]] = query(r[o[i]]) - query(l[o[i]]);
		change(r[o[i]], 1);
	}
	for (int i = 1; i <= n; i++)
	{
		printf("%d\n", z[i]);
	}
	return 0;
}

题解

http://usaco.org/index.php?page=viewproblem2&cpid=696

DFS序
离散化

方法一

DFS求进出栈序
对DFS序建树状数组
按(能力，下标)排序
扫描所有奶牛
询问自己子树的和（比自己能力高的一定先加入）
把自己改成1

将所有点按权值排序是

5 957747794
2 846930887
1 804289384
4 714636916
3 681692778

DFS序和每个点对应的区间是

1 2 4 4 2 3 5 5 3 1
+ + + - - + + - - -

 1 2 4 3 5
[         ] 1
  [   ]     2
    [ ]     4
      [   ] 3
        [ ] 5

权值从大到小依次处理，先查询，再修改

 0 0 0 0[0]            z[5] = 0
 0[0 0]0 1  a[5] += 1, z[2] = 0
[0 1 0 0 1] a[2] += 1, z[1] = 2
 1 1[0]0 1  a[1] += 1, z[4] = 0
 1 1 1[0 1] a[4] += 3, z[3] = 1
 1 1 1 1 1  a[3] += 1

最后可以得到答案 [2, 0, 1, 0, 0]

方法二

对权值建树状数组
以样例为例，离散化后，相当于每个点的权值是

1 3
2 4
3 1
4 2
5 5

考虑进出栈序

1 2 2 3 4 4 5 5 3 1
+ + - + + - + - - -

对于每个点询问两次：

• 自己第一次出现的左侧有多少个权值比自己大
• 自己第二次出现的左侧有多少个权值比自己大

两次的差就是在自己子树中有多少个权值比自己大

P5094 [USACO04OPEN] MooFest G 加强版

https://www.luogu.com.cn/problem/P5094

题目背景

题目描述

每一年，约翰的 $N$ 只奶牛参加奶牛狂欢节。这是一个全世界奶牛都参加的大联欢。狂欢节包括很多有趣的活动，比如干草堆叠大赛、跳牛栏大赛，奶牛之间有时还相互扎屁股取乐。当然，她们会排成一列嚎叫，来欢庆她们的节日。奶牛们的叫声实在刺耳，以致于每只奶牛的听力都受到不同程度的损伤。现在告诉你奶牛 $i$ 的听力为 $v_i$ ，这表示如果奶牛 $j$ 想说点什么让她听到，必须用高于 $v_i \times dis(i,j)$ 的音量。因此，如果奶牛 $i$ 和 $j$ 想相互交谈，她们的音量必须不小于 $\max (v_i,v_j) \times dis(i,j)$。其中 $dis(i,j)$ 表示她们间的距离。

现在 $N$ 只奶牛都站在一条直线上了，每只奶牛还有一个坐标 $x_i$。如果每对奶牛都在交谈，并且使用最小音量，那所有 $N(N-1)/2$ 对奶牛间谈话的音量之和为多少？

输入格式

第 $1$ 行输入一个整数 $N$ 。

接下来 $N$ 行，每行输入两个数 $v_i$ 和 $x_i$ ，分别代表第 $i$ 头奶牛的听力和坐标。

输出格式

输出一个数，代表这 $N(N-1)/2$ 对奶牛谈话时的音量之和。

样例 #1

样例输入 #1

4
3 1
2 5
2 6
4 3

样例输出 #1

57

提示

数据范围

因为原数据下 $O(N^2)$ 算法可以通过，所以新添加了一些增强数据。

原数据作为子任务 $1$，新添加的数据作为子任务 $2$。

• 子任务 $1$（$1$ 分）：$1 \leq N,V_i,x_i \leq 2 \times 10^4$。
• 子任务 $2$（$99$ 分）：$1 \leq N,V_i,x_i \leq 5 \times 10^4$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
pair<int, int> a[50020];
long long c[50020];
long long d[50020];
long long s, z;
void change(long long *c, int x, int y)
{
	for (; x < 50010; x += x & -x)
	{
		c[x] += y;
	}
}
long long query(long long *c, int x)
{
	long long re = 0;
	for (; x > 0; x -= x & -x)
	{
		re += c[x];
	}
	return re;
}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", &a[i].first, &a[i].second);
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++)
	{
		z += (s - 2 * query(d, a[i].second) - (i - 2 * query(c, a[i].second)) * a[i].second) * a[i].first;
		s += a[i].second;
		change(c, a[i].second, 1);
		change(d, a[i].second, a[i].second);
	}
	printf("%lld\n", z);
	return 0;
}

题解

https://vjudge.net/problem/POJ-1990

排序所有的牛，按音量升序
sort all cows by their volume threshold increasing order

for (int i = 0; i < n; i++)
{
ans += (the sum of all distances)* volume threshold[i];
}

距离有2种可能，左边和右边

4
2 5
2 6
3 1
4 3

num 0 0 0 0 0 0
sum 0 0 0 0 0 0
answer = 0
num 0 0 0 0 1 0
sum 0 0 0 0 5 0
answer = 0 + (1 * 6 - 5) * 2 = 2
num 0 0 0 0 1 1
sum 0 0 0 0 5 6
answer = 2 + ((5 + 6) - 2 * 1) * 3 = 29
num 1 0 0 0 1 1
sum 1 0 0 0 5 6
answer = 29 + (1 * 3 - 1) * 4 + ((5 + 6) - 2 * 3) * 4 = 57
num 1 0 1 0 1 1
sum 1 0 3 0 5 6

左边：
(the number of cows on our left * a[i].x - the sum of x of the cows on our left)

右边：
(the sum of x of the cows on our right - the number of cows on our right * a[i].x)

加在一起
(the number of cows on our left - the number of cows on our right) * a[i].x
+
(the sum of x of the cows on our right - the sum of x of the cows on our left)

(左边的个数 - (总数 - 左边的个数)) * a[i].x
+
((总坐标之和 - 左边的坐标之和) - 左边的坐标之和)

(2 * 左边的个数 - 总数) * a[i].x + (总坐标之和 - 2 * 左边的坐标之和)

https://vjudge.net/problem/POJ-1195

https://vjudge.net/problem/POJ-2155

https://vjudge.net/problem/POJ-2352
输入已经排序好了（y升序，y相等的话按x升序）

对x轴维护一个树状数组

对于每个点(x, y):
询问树状数组中 <= x 位置的和（这些点在自己的左下方
树状数组的x位置++

一些特殊情况
在这个题目中，给出X, Y
询问有多少个点x[i] <= X && y[i] <= Y

如果是
x[i] < X && y[i] < Y
x[i] <= X && y[i] < Y
x[i] < X && y[i] <= Y
x[i] <= X && y[i] <= Y

分别应该怎么做？
如果是x[i] < X，那么在树状数组询问 < x的位置 的和（而不是 <= x）
如果是y[i] < Y，那么如果y相等，按x降序

如果点重合怎么办？（没考虑

https://vjudge.net/problem/POJ-2828
https://www.cnblogs.com/ZhaoxiCheung/p/5782487.html

poj 2828 Buy Tickets

http://poj.org/problem?id=2828

倒序考虑，询问第$k$个$1$。

倒序考虑所有人
如果插入在了第pos个人的后面，相当于问第pos+1个1是谁？
把自己放在这个位置，把1改成0

Buy Tickets

Find the k-th 1 in the orginal array a[].
找第k个1
We assume that there are only 0 and 1 in the array a[]
假设a数组中只有和0和1
Find the index of x-th 1 in the array a[]
问a数组中第k个1是什么？

直接二分，既然x是第k个1，那么一定满足query(x) >= k && query(x-1) < k
Use binary search
Because x is the index of the k-th 1 in the array,
it must satisfy query(x) >= k and query(x-1) < k

(x == re + 1)

int ask(int x) // 第x个1
{
    int re = 0; // 保证任何时候 query(re) < x
    for (int i = 1 << 20; i > 0; i /= 2)
    {
        if (re + i <= n && x > c[re + i]) // 如果 query(re + i)之后还是<x
        {
            re += i; // 把 re 改成 re + i
            x -= c[re];
        }
    }
    // re is the largest, which satisfy query(re) < x
    // query(re + 1) >= x
    return re + 1;
}


@import "problems/P2345" [USACO04OPEN]MooFest G
@import "problems/P5142" 区间方差
@import "problems/P3801" 红色的幻想乡

poj 2155

poj 2155 Matrix
二维的差分
2D difference

change time complexity: O(log^2 n)

a[i][j] = sum of b[1..i][1..j]

b[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]

For this problem, we use BIT to maintain b[i][j]

when we change x1 <= x <= x2, y1 <= y <= y2, we change
b[x1][y1]
b[x1][y2+1]
b[x2+1][y1]
b[x2+1][y2+1]

修改 x1 <= x <= x2, y1 <= y <= y2
相当于修改
x2++;
y2++;
change(x1, y1, 1);
change(x1, y2, 1);
change(x2, y1, 1);
change(x2, y2, 1);

void change(int x, int y, int z)
{
for (int i = x; i <= n; i += i & -i)
{
for (int j = y; j <= n; j += j & -j)
{
c[i][j] += z;
}
}
}

void query(int x, int y, int z)
{
int re = 0;
for (int i = x; i > 0; i -= i & -i)
{
for (int j = y; j > 0; j -= j & -j)
{
re += c[i][j];
}
}
return re;
}

poj 1195 Mobile phones

必须从1开始下标

poj 2352 Stars

2D problem, sort 1D, use BIT to solve another D

排序所有点（输入已经是有序的了）
sort all points (the input is sorted)
如果先按y从小到大，y相同按x从小到大排序

ans[query(x)]++;
change(x, 1);

x可能有0，需要++
现在题目中问的是 xi <= x, yi <= y
改成 xi < x, yi <= y 怎么做？
ans[query(x - 1)]++;
change(x, 1);

改成 xi <= x, yi < y 怎么做？
排序需要注意，
先按y从小到大，y相同按x从大到小排序

改成 xi < x, yi < y 怎么做？
排序需要注意，
先按y从小到大，y相同按x从大到小排序
ans[query(x - 1)]++;
change(x, 1);

对于所有问题都需要特别注意有没有重合的(x, y)

P3605 [USACO17JAN]Promotion Counting P

https://www.luogu.com.cn/problem/P3605

题目背景

题目描述

The cows have once again tried to form a startup company, failing to remember from past experience that cows make terrible managers!

The cows, conveniently numbered $1 \ldots N$ ($1 \leq N \leq 100,000$), organize the company as a tree, with cow 1 as the president (the root of the tree). Each cow except the president has a single manager (its "parent" in the tree). Each cow $i$ has a distinct proficiency rating, $p(i)$, which describes how good she is at her job. If cow $i$ is an ancestor (e.g., a manager of a manager of a manager) of cow $j$, then we say $j$ is a subordinate of $i$.

Unfortunately, the cows find that it is often the case that a manager has less proficiency than several of her subordinates, in which case the manager should consider promoting some of her subordinates. Your task is to help the cows figure out when this is happening. For each cow $i$ in the company, please count the number of subordinates $j$ where $p(j) > p(i)$.

奶牛们又一次试图创建一家创业公司，还是没有从过去的经验中吸取教训--牛是可怕的管理者！

为了方便，把奶牛从 $1\sim n$ 编号，把公司组织成一棵树，1 号奶牛作为总裁（这棵树的根节点）。除了总裁以外的每头奶牛都有一个单独的上司（它在树上的 “双亲结点”）。

所有的第 $i$ 头牛都有一个不同的能力指数 $p_i$，描述了她对其工作的擅长程度。如果奶牛 $i$ 是奶牛 $j$ 的祖先节点，那么我们我们把奶牛 $j$ 叫做 $i$ 的下属。

不幸地是，奶牛们发现经常发生一个上司比她的一些下属能力低的情况，在这种情况下，上司应当考虑晋升她的一些下属。你的任务是帮助奶牛弄清楚这是什么时候发生的。简而言之，对于公司的中的每一头奶牛 $i$，请计算其下属 $j$ 的数量满足 $p_j > p_i$。

输入格式

The first line of input contains $N$.

The next $N$ lines of input contain the proficiency ratings $p(1) \ldots p(N)$ for the cows. Each is a distinct integer in the range $1 \ldots 1,000,000,000$.

The next $N-1$ lines describe the manager (parent) for cows $2 \ldots N$. Recall that cow 1 has no manager, being the president.

输入的第一行包括一个整数 $n$。

接下来的 $n$ 行包括奶牛们的能力指数 $p_1,p_2 \dots p_n$。保证所有数互不相同。

接下来的 $n-1$ 行描述了奶牛 $2 \sim n$ 的上司的编号。再次提醒，1 号奶牛作为总裁，没有上司。

输出格式

Please print $N$ lines of output. The $i$th line of output should tell the number of subordinates of cow $i$ with higher proficiency than cow $i$.

输出包括 $n$ 行。输出的第 $i$ 行应当给出有多少奶牛 $i$ 的下属比奶牛 $i$ 能力高。

样例 #1

样例输入 #1

5
804289384
846930887
681692778
714636916
957747794
1
1
2
3

样例输出 #1

2
0
1
0
0

提示

感谢@rushcheyo 的翻译

【数据范围】
对于 $100\%$ 的数据，$1\le n \le 10^5$，$1 \le p_i \le 10^9$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, ss, x;
vector<int> a[100020];
int p[100020];
int o[100020];
int l[100020];
int r[100020];
int c[100020];
int z[100020];
void dfs(int x)
{
	l[x] = ss;
	for (int i: a[x])
	{
		dfs(i);
	}
	r[x] = ++ss;
}
void change(int x, int y)
{
	for (; x <= n; x += x & -x)
	{
		c[x] += y;
	}
}
int query(int x)
{
	int re = 0;
	for (; x > 0; x -= x & -x)
	{
		re += c[x];
	}
	return re;
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &p[i]);
		o[i] = i;
	}
	sort(o + 1, o + 1 + n, [](int x,int y){return p[x]>p[y];});
	for (int i = 2; i <= n; i++)
	{
		scanf("%d", &x);
		a[x].push_back(i);
	}
	dfs(1);
	for (int i = 1; i <= n; i++)
	{
		z[o[i]] = query(r[o[i]]) - query(l[o[i]]);
		change(r[o[i]], 1);
	}
	for (int i = 1; i <= n; i++)
	{
		printf("%d\n", z[i]);
	}
	return 0;
}

题解

http://usaco.org/index.php?page=viewproblem2&cpid=696

DFS序
离散化

方法一

DFS求进出栈序
对DFS序建树状数组
按(能力，下标)排序
扫描所有奶牛
询问自己子树的和（比自己能力高的一定先加入）
把自己改成1

将所有点按权值排序是

5 957747794
2 846930887
1 804289384
4 714636916
3 681692778

DFS序和每个点对应的区间是

1 2 4 4 2 3 5 5 3 1
+ + + - - + + - - -

 1 2 4 3 5
[         ] 1
  [   ]     2
    [ ]     4
      [   ] 3
        [ ] 5

权值从大到小依次处理，先查询，再修改

 0 0 0 0[0]            z[5] = 0
 0[0 0]0 1  a[5] += 1, z[2] = 0
[0 1 0 0 1] a[2] += 1, z[1] = 2
 1 1[0]0 1  a[1] += 1, z[4] = 0
 1 1 1[0 1] a[4] += 3, z[3] = 1
 1 1 1 1 1  a[3] += 1

最后可以得到答案 [2, 0, 1, 0, 0]

方法二

对权值建树状数组
以样例为例，离散化后，相当于每个点的权值是

1 3
2 4
3 1
4 2
5 5

考虑进出栈序

1 2 2 3 4 4 5 5 3 1
+ + - + + - + - - -

对于每个点询问两次：

• 自己第一次出现的左侧有多少个权值比自己大
• 自己第二次出现的左侧有多少个权值比自己大

两次的差就是在自己子树中有多少个权值比自己大

https://loj.ac/problem/135

P4514 上帝造题的七分钟

https://www.luogu.com.cn/problem/P4514

题目背景

裸体就意味着身体。

题目描述

“第一分钟，X 说，要有矩阵，于是便有了一个里面写满了 $0$ 的 $n\times m$ 矩阵。

第二分钟，L 说，要能修改，于是便有了将左上角为 $(a,b)$，右下角为 $(c,d)$ 的一个矩形区域内的全部数字加上一个值的操作。

第三分钟，k 说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。

第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。

第五分钟，和雪说，要有耐心，于是便有了时间限制。

第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过 $32$ 位有符号整数类型的表示范围的限制。

第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”。

——《上帝造裸题的七分钟》。

所以这个神圣的任务就交给你了。

输入格式

输入数据的第一行为 X n m，代表矩阵大小为 $n\times m$。
从输入数据的第二行开始到文件尾的每一行会出现以下两种操作：

• L a b c d delta —— 代表将 $(a,b),(c,d)$ 为顶点的矩形区域内的所有数字加上 $delta$。
• k a b c d —— 代表求 $(a,b),(c,d)$ 为顶点的矩形区域内所有数字的和。

请注意，$k$ 为小写。

输出格式

针对每个 $k$ 操作，在单独的一行输出答案。

样例 #1

样例输入 #1

X 4 4
L 1 1 3 3 2
L 2 2 4 4 1
k 2 2 3 3

样例输出 #1

12

提示

对于 $10\%$ 的数据，$1 \le n \le 16$，$1 \le m \le 16$， 操作不超过 $200$ 个。

对于 $60\%$ 的数据，$1 \le n \le 512$，$1 \le m \le 512$。

对于 $100\%$ 的数据，$1 \le n \le 2048$，$1 \le m \le 2048$，$-500 \le delta \le 500$，操作不超过 $2\times 10^5$ 个，保证运算过程中及最终结果均不超过 $32$ 位带符号整数类型的表示范围。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[2049][2049];
int b[2049][2049];
int c[2049][2049];
int d[2049][2049];
void change(int x, int y, int z)
{
	for (int i = x; i <= n; i += i & -i)
	{
		for (int j = y; j <= m; j += j & -j)
		{
			a[i][j] += z;
			b[i][j] += z * x;
			c[i][j] += z * y;
			d[i][j] += z * x * y;
		}
	}
}
int query(int x, int y)
{
	int ra = 0, rb = 0, rc = 0, rd = 0;
	for (int i = x; i > 0; i -= i & -i)
	{
		for (int j = y; j > 0; j -= j & -j)
		{
			ra += a[i][j];
			rb += b[i][j];
			rc += c[i][j];
			rd += d[i][j];
		}
	}
	return ra * (x + 1) * (y + 1) - rb * (y + 1) - rc * (x + 1) + rd;
}
int main()
{
	scanf("X %d %d", &n, &m);
	for (char o; ~scanf(" %c", &o);)
	{
		int x1, y1, x2, y2, z;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		if (o == 'L')
		{
			scanf("%d", &z);
			change(x1, y1, z);
			change(x1, y2 + 1, -z);
			change(x2 + 1, y1, -z);
			change(x2 + 1, y2 + 1, z);
		}
		else
		{
			printf("%d\n", query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1));
		}
	}
	return 0;
}

题解

ans =
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j]

a is 2D prefix sum of b
b is the difference array of a

a[i][j] =
for (int k = 1; k <= i; k++)
for (int l = 1; l <= j; l++)
b[k][l]

ans =
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= i; k++)
for (int l = 1; l <= j; l++)
b[k][l]

ans =
for (int k = 1; k <= n; k++)
for (int l = 1; l <= m; l++)
for (int i = k; i <= n; i++)
for (int j = l; j <= n; j++)
b[k][l]

ans =
for (int k = 1; k <= n; k++)
for (int l = 1; l <= m; l++)
b[k][l] * (n - k + 1) * (m - l + 1)

into 4 parts
b[k][l]
b[k][l] * k
b[k][l] * l
b[k][l] * k * l

求
s[i] = a[1] + a[2] + ... + a[i]

s[1] + s[2] + ... + s[x] =
x*a[1] + (x-1)*a[2] + (x-2)a[3] + ... + 1a[x]

(x+1-i) * a[i]

(x+1) * (a[1] + a[2] + ... + a[x]) -
(1a[1] + 2a[2] + ... + x * a[x])

数组a
array a
数组b是数组a的前缀和
array b is the prefix sum of array a
数组c是数组b的前缀和
array c is the prefix sum of array b
数组d是数组c的前缀和
array d is the prefix sum of array c

修改a[x] = y
change a[x] = y
问d数组中的一项d[x]
query d[x]

d[x] =
for (int i = 1; i <= x; i++)
c[i]

d[x] =
for (int i = 1; i <= x; i++)
for (int j = 1; j <= i; j++)
b[j]

d[x] =
for (int i = 1; i <= x; i++)
for (int j = 1; j <= i; j++)
for (int k = 1; k <= j; k++)
a[k]

d[x] =
for (int k = 1; k <= j; k++)
a[k] * (the number of i, j such that k <= j <= i <= x)

d[x] =
for (int k = 1; k <= j; k++)
a[k] * (x + 1 - k) * (x + 2 - k) / 2

into 3 parts
c[k]
c[k] * k
c[k] * k * k

poj 3468的二维版本。
据说有CDQ分治相关的方法。

希望求 s[n][m]

s[n][m] = sum(a[i][j], 1 <= i <= n, 1 <= j <= m)
a[i][j] = sum(b[k][l], 1 <= k <= i, 1 <= l <= j)

s[n][m] = sum(sum(b[k][l], 1 <= k <= i, 1 <= l <= j), 1 <= i <= n, 1 <= j <= m)
s[n][m] = sum(sum(b[k][l] * (n+1-k) * (m+1-l), 1 <= k <= n, 1 <= l <= m))

用二维树状数组维护 b[k][l]
用二维树状数组维护 b[k][l] * k
用二维树状数组维护 b[k][l] * l
用二维树状数组维护 b[k][l] * k * l

b[k][l] * (n+1-k) * (m+1-l) =
b[k][l] * ((n+1) * (m+1) - k * (m+1) - l * (n+1) + k * l)

P2344 [USACO11FEB]Generic Cow Protests G

https://www.luogu.com.cn/problem/P2344

题目背景

题目描述

Farmer John 的 $N$ 头奶牛（$1 \leq N \leq 10^5$）排成一列，正在进行一场抗议活动。第 $i$ 头奶牛的理智度为 $a_i$（$-10^4 \leq a_i \leq 10^4$）。

FJ 希望奶牛在抗议时保持理性，为此，他打算将所有的奶牛隔离成若干个小组，每个小组内的奶牛的理智度总和都要不小于零。

由于奶牛是按直线排列的，所以一个小组内的奶牛位置必须是连续的。请帮助 FJ 计算一下，满足条件的分组方案有多少种。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行一个整数，第 $i$ 行的整数表示第 $i$ 头奶牛的理智度 $a_i$。

输出格式

输出满足条件的分组方案对 $10^9+9$ 取模的结果。

样例 #1

样例输入 #1

4
2
3
-3
1

样例输出 #1

4

提示

所有合法分组方案如下：

• $\texttt{(2 3 -3 1)}$
• $\texttt{(2 3 -3) (1)}$
• $\texttt{(2) (3 -3 1)}$
• $\texttt{(2) (3 -3) (1)}$

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[100020], n;
int l[100020], lc;
int c[100020], f;
int mod = 1000000009;
void change(int x, int y)
{
	for (int i = x; i <= lc; i += i & -i)
	{
		c[i] = (c[i] + y) % mod;
	}
}
int query(int x)
{
	int re = 0;
	for (int i = x; i > 0; i -= i & -i)
	{
		re = (re + c[i]) % mod;
	}
	return re;
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		a[i] += a[i - 1];
		l[i] = a[i];
	}
	lc = n + 1;
	sort(l, l + lc);
	lc = unique(l, l + lc) - l;
	for (int i = 0; i <= n; i++)
	{
		a[i] = lower_bound(l, l + lc, a[i]) - l + 1;
	}
	change(a[0], 1);
	for (int i = 1; i <= n; i++)
	{
		change(a[i], f = query(a[i]));
	}
	printf("%d\n", f);
	return 0;
}

题解

前缀和
s[i] = a[1] + a[2] + .. + a[i]
s[0] = 0

s[0] s[1] s[2] ... s[n]
求有多少个不下降的子序列，s[0]和s[n]必须选择

s[0] s[1] s[3] s[4]
s[0] <= s[1] <= s[3] <= s[4]
(a[1]) (a[2] a[3]) (a[4])

f[0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < i; j++)
{
if (s[i] >= s[j])
{
f[i] += f[j];
}
}
}
printf("%d\n", f[n]);

(i, s[i])

前缀和

s[i] = a[1] + a[2] + .. + a[i]

s[0] = 0

s[0] s[1] s[2] ... s[n]
求有多少个不下降的子序列，s[0]和s[n]必须选择

s[0] s[1] s[3] s[4]
s[0] <= s[1] <= s[3] <= s[4]
(a[1]) (a[2] a[3]) (a[4])

f[0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < i; j++)
{
if (s[i] >= s[j])
{
f[i] += f[j];
}
}
}
printf("%d\n", f[n]);

(i, s[i])

线段树 扫描线
Luogu P5490

这些楼里能看到几个
最高的一个楼是什么

P6098 [USACO19FEB]Cow Land G

https://www.luogu.com.cn/problem/P6098

题目背景

Cow Land 是一个特殊的奶牛游乐园，奶牛们可以在那里漫步，吃美味的草，并参观不同的景点（尤其过山车特别受欢迎）。

题目描述

Cow Land 总共有 $N$ 个不同的景点（ $2 \leq N \leq 10^5$ ）。 一共有 $n-1$ 条道路连接任意两个景点，这意味着任意两个景点间只有一条简单路径。

每个景点 $i$ 都有一个享受值 $e_i$ ，这个值可能会改变。因为一些景点在早上更有吸引力，而其他景点在下午则更能吸引游客。

从景点 $i$ 到景点 $j$ 的奶牛们可以欣赏从景点 $i$ 到景点 $j$ 的路上的所有景观。这条路线的享受值为景点 $i$ 到景点 $j$ 的路上的所有景点（包括景点 $i$ 和景点 $j$ ）的享受值按位进行异或运算的结果。

请帮助奶牛确定他们前往 Cow Land 旅行时计划的路线的享受值。

输入格式

输入的第一行包含两个整数， $N,Q$（$1 \leq Q \leq 10^5$）。

接下来一行包含 $N$ 个整数，其中第 $i$ 个整数 $e_i$ 代表景点 $i$ 的享受值。

接下来 $N-1$ 行，每行包含两个整数 $a,b$ ，表示景点 $a$ 和景点 $b$ 之间有一条道路相连。

最后 $Q$ 行，每行包含 3 个整数，表示一个操作，具体内容如下：

1. 1 i v，表示将 $e_i$ 修改为 $v$ 。
2. 2 i j，表示询问从景点 $i$ 到景点 $j$ 的路线的享受值为多少。

输出格式

对于每个 2 操作，输出对应查询的结果。

样例 #1

样例输入 #1

5 5
1 2 4 8 16
1 2
1 3
3 4
3 5
2 1 5
1 1 16
2 3 5
2 1 5
2 1 3

样例输出 #1

21
20
4
20

提示

子任务：对于 $50\%$ 的数据，没有修改操作。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, q;
vector<int> a[100020];
int f[100020][20];
int d[100020];
int c[200020];
int w[100020];
int L[100020];
int R[100020];
int ss = 1;
void change(int x, int y) {
	for (int i = x; i <= 2 * n; i += i & -i) {
		c[i] ^= y;
	}
}
int query(int x) {
	int re = 0;
	for (int i = x; i > 0; i -= i & -i) {
		re ^= c[i];
	}
	return re;
}
void dfs(int x, int y) {
	f[x][0] = y;
	d[x] = d[y] + 1;
	for (int i = 1; i < 20; i++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	L[x] = ss;
	ss++;
	for (int i: a[x]) {
		if (i != y) {
			dfs(i, x);
		}
	}
	R[x] = ss;
}
int lca(int x, int y) {
	if (d[x] < d[y]) {
		swap(x, y);
	}
	int dd = d[x] - d[y];
	for (int i = 0; i < 20; i++) {
		if (dd >> i & 1) {
			x = f[x][i];
		}
	}
	if (x == y) {
		return x;
	}
	for (int i = 20 - 1; i >= 0; i--) {
		if (f[x][i] != f[y][i]) {
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
int main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
	}
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	dfs(1, 0);
	for (int i = 1; i <= n; i++) {
		change(L[i], w[i]);
		change(R[i], w[i]);
	}
	for (int i = 0; i < q; i++) {
		int o, x, y;
		cin >> o >> x >> y;
		if (o == 1) {
			change(L[x], w[x] ^ y);
			change(R[x], w[x] ^ y);
			w[x] = y;
		} else {
			cout << (query(L[x]) ^ query(L[y]) ^ w[lca(x, y)]) << endl;
		}
	}
	return 0;
}

题解

用来和树状数组配合的是进出栈序
有两种使用方法

修改单点，询问子树和
把点权放在第一次出现的位置上
子树和就是区间和

修改单点，询问根节点到某节点的路径和
在第一次出现的位置上加上点权
在第二次出现的位置上减去点权
1 2 2 3 4 4 5 5 3 1

• • • • • • • ---

实际实现的时候，可以第二次出现位置不+1
0 1 2 3 4 5 6
1 1
2 2
3 3
4 4
5 5

0 1 2 3 4 5 6 7 8 9 10
1 1
2 2
3 3
4 4
5 5

abc185_f

https://atcoder.jp/contests/abc185/tasks/abc185_f
异或树状数组

CF1660F2

https://codeforces.com/problemset/problem/1660/F2

spoj DEV_CP

https://www.spoj.com/problems/DEV_CP/