树状数组#

算法思想#

树状数组核心思想：用二进制分解的思想，将一个数组的前缀和或单点更新操作优化到 O(log⁡n)。树状数组利用二进制最低位（lowbit）来组织数据，每个节点 tree[i] 维护原数组区间 (i - lowbit(i), i] 的信息。更新时沿着索引增加 lowbit 的方向向上修改；查询前缀和时沿着索引减少 lowbit 的方向向下累加。本质是用空间换时间，将线性操作转化为树形结构的跳跃式聚合。

归并排序核心思想：基于分治的经典排序算法。将数组不断二分为左右两个子数组，直到每个子数组长度为 1（天然有序）；然后通过两路归并，将两个已排序的子数组合并成一个更大的有序数组。合并时，依次比较两个子数组的头部元素，将较小的放入临时数组，直到所有元素归并完成。归并排序保证 O(nlogn) 的时间复杂度，且是稳定排序。

[单点修改] + [区间查询]#

树状数组提供了 [单点修改] + [区间查询] 的一种方法

对于求一段前缀和a[1…7]，最朴素的方法是 $a_1$ + $a_2$ +··· $a_7$

然而，若已知A=a[1…4]，B=[5…6]，C=[7…7]，那么这段前缀和就等于A+B+C

显然的第二种方法只需要知道三个已知数

总能够将一段前缀[1…n]拆成不多于 $log_n$ 段区间，使得这些区间的信息是已知的；只需要合并这些区间就能得到前缀和的答案

在树状数组中这些区间的划分依赖于当前数的二进制到该二进制去掉最低位的1后再加1后得到的区间

区间查询#

对于88，其二进制位01011000，其管辖的范围为01011000~01010001，即81~88

其实现方法为x&-x

那么对于求 $a_1$ + $a_2$ +··· $a_7$ ，按照上面的划分规则，b7管辖的是a7；b6管辖的是a5、a6；b4管辖的是a1~a4；那么所求即为b7 + b6 + b4

1
def getsum(x):  # a[1]..a[x]的和
2
    ans = 0
3
    while x > 0:
4
        ans = ans + c[x]
5
        x = x - lowbit(x)
6
    return ans

单点修改#

只需要遍历并修改管辖了a[x]的所有点即可

1
def add(x, k):
2
    while x <= n:  # 不能越界
3
        c[x] = c[x] + k
4
        x = x + lowbit(x)

模板-洛谷P3374#

问题描述#

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

将某一个数加上 x；
求出某区间每一个数的和。

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

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

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

1 x k 含义：将第 x 个数加上 k；
2 x y 含义：输出区间 [x,y] 内每个数的和。

树状数组#

1
class FenwickTree:
2
    def __init__(self, length):
3
        self.length = length
4
        self.tree = [0] * (length + 1)
5

6
    def lowbit(self, x):
7
        return x & -x
8
    # 单点修改
9
    def update(self, idx, val):
10
        while idx <= self.length:
11
            self.tree[idx] += val
12
            idx += self.lowbit(idx)
13
    # 区间求和
14
    def query(self, idx):
15
        res = 0
16
        while idx > 0:
17
            res += self.tree[idx]
18
            idx -= self.lowbit(idx)
19
        return res
20

21
n,m = map(int,input().split())
22
a = [0] + list(map(int,input().split()))
23
# 初始化树状数组
24
bit = FenwickTree(n)
25
for i in range(1,n+1):
26
    bit.update(i,a[i])
27
for _ in range(m):
28
    op,x,y = map(int,input().split())
29
    if op == 1:
30
        bit.update(x,y)
31
    else:
32
        print(bit.query(y) - bit.query(x-1))

洛谷P16799逆元+维护两个树状数组#

题目#

小蓝正在帮助老师统计实验数据。

一共有 $n$ 次实验，第 $i$ 次实验的参数为 $i$ ，对应的实验数据为 $a_i$ 。为了分析实验参数与实验数据之间的关系，小蓝需要多次查询某个连续区间内实验数据的平均值。为了衡量实验结果的稳定性，他还需要查询该区间内实验数据的方差。

此外，小蓝可能会重新进行某一次实验。若重新进行了第 $k$ 次实验，则原来的 $a_k$ 会被替换为新的实验数据。

对于一次区间查询 $[l, r]$ ，记区间长度为 $\textit{len} = r - l + 1$ ，区间平均值为

\bar{a} = \frac{\sum_{i=l}^r a_i}{\textit{len}}.

本题中，区间方差定义为

\mathrm{Var} = \sum_{i=l}^r (a_i - \bar{a})^2.

你需要支持两类操作：

查询区间 $[l, r]$ 的平均值与方差；
将某个位置 $k$ 的实验数据修改为 $x$ 。

由于答案可能是有理数，为避免精度误差，所有查询结果均在模 $998244353$ 的意义下输出。

具体地，设某个答案为有理数 $x$ 。将 $x$ 表示为最简分数

x = \frac{p}{q},

其中 $p$ 和 $q$ 为整数， $q > 0$ ，且 $\gcd(p, q) = 1$ 。本题保证 $q$ 与 $998244353$ 互质。

请输出一个整数 $y$ ，满足

\begin{aligned} 0 \le y < 998244353, y \equiv p \cdot q^{-1} \pmod{998244353}, \end{aligned}

这里的 $q^{-1}$ 表示 $q$ 在模 $998244353$ 意义下的乘法逆元。

第一行包含两个正整数 $n, m$ ，分别表示实验次数和操作次数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ，表示初始实验数据。

接下来 $m$ 行，每行描述一个操作，格式为以下两种之一：

1 l r：查询区间 $[l, r]$ 内实验数据的平均值和方差；
2 k x：将 $a_k$ 修改为 $x$ 。

逆元+维护两个树状数组#

平均值

\bar{a} = \frac{\sum a_i}{len}

方差

Var = \sum (a_i - \bar{a})^2 = \sum a_i^2 - 2\bar{a}\sum a_i + len \cdot \bar{a}^2

代入 $\bar{a} = \frac{S_1}{len}$ ：

Var = \sum a_i^2 - 2 \cdot \frac{S_1}{len} \cdot S_1 + len \cdot \frac{S_1^2}{len^2} = S_2 - \frac{2S_1^2}{len} + \frac{S_1^2}{len} = S_2 - \frac{S_1^2}{len}

其中 $S_1 = \sum a_i$ ， $S_2 = \sum a_i^2$ 。

所以在模意义下：

\bar{a} = S_1 \cdot len^{-1} \pmod{998244353}

Var = S_2 - S_1^2 \cdot len^{-1} \pmod{998244353}

需要支持：

单点修改： $a_k \to x$ ，更新 $S_1$ 和 $S_2$
区间查询：查询 $[l, r]$ 的 $S_1$ 和 $S_2$

用两个树状数组维护：

bit1：维护 $\sum a_i$
bit2：维护 $\sum a_i^2$

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
const long long MOD = 998244353;
5

6
long long mod_pow(long long a, long long b) {
7
    long long res = 1;
8
    while (b) {
9
        if (b & 1) res = res * a % MOD;
10
        a = a * a % MOD;
11
        b >>= 1;
12
    }
13
    return res;
14
}
15

16
struct Fenwick {
17
    int n;
18
    vector<long long> tree;
19
    Fenwick(int n) : n(n), tree(n + 1, 0) {}
20

21
    void add(int idx, long long val) {
22
        val = (val % MOD + MOD) % MOD;
23
        for (; idx <= n; idx += idx & -idx) {
24
            tree[idx] = (tree[idx] + val) % MOD;
25
        }
26
    }
27

28
    long long sum(int idx) {
29
        long long res = 0;
30
        for (; idx > 0; idx -= idx & -idx) {
31
            res = (res + tree[idx]) % MOD;
32
        }
33
        return res;
34
    }
35

36
    long long range_sum(int l, int r) {
37
        return (sum(r) - sum(l - 1) + MOD) % MOD;
38
    }
39
};
40

41
int main() {
42
    ios::sync_with_stdio(false);
43
    cin.tie(0);
44

45
    int n, m;
46
    cin >> n >> m;
47

48
    Fenwick bit1(n), bit2(n);
49
    vector<long long> a(n + 1, 0);
50

51
    for (int i = 1; i <= n; i++) {
52
        cin >> a[i];
53
        bit1.add(i, a[i]);
54
        bit2.add(i, a[i] * a[i] % MOD);
55
    }
56

57
    // 预计算逆元
58
    vector<long long> inv(n + 1);
59
    for (int i = 1; i <= n; i++) {
60
        inv[i] = mod_pow(i, MOD - 2);
61
    }
62

63
    while (m--) {
64
        int op;
65
        cin >> op;
66

67
        if (op == 1) {
68
            int l, r;
69
            cin >> l >> r;
70

71
            long long len = r - l + 1;
72
            long long inv_len = inv[len];
73

74
            long long S1 = bit1.range_sum(l, r);
75
            long long S2 = bit2.range_sum(l, r);
76

77
            // 平均值 = S1 / len
78
            long long avg = S1 * inv_len % MOD;
79

80
            // 方差 = S2 - S1^2 / len
81
            long long var = (S2 - S1 * S1 % MOD * inv_len % MOD + MOD) % MOD;
82

83
            cout << avg << ' ' << var << '\n';
84
        } else {
85
            int k;
86
            long long x;
87
            cin >> k >> x;
88

89
            long long old = a[k];
90
            if (old == x) continue;
91

92
            // 更新 S1
93
            bit1.add(k, x - old);
94

95
            // 更新 S2：x^2 - old^2
96
            long long diff = (x * x % MOD - old * old % MOD + MOD) % MOD;
97
            bit2.add(k, diff);
98

99
            a[k] = x;
100
        }
101
    }
102

103
    return 0;
104
}

1
vector<long long> inv(n + 1);
2
for (int i = 1; i <= n; i++) {
3
    inv[i] = mod_pow(i, MOD - 2);
4
}

区间长度最大 $3 \times 10^5$ ，预计算所有逆元避免每次快速幂。

更新时：

1
bit1.add(k, x - old);  // diff 可能为负，add 内部处理
2
bit2.add(k, (x*x - old*old) % MOD);

用费马小定理：inv = mod_pow(x, MOD-2)（MOD 是质数）

MT2142#

题目#

给一个长度为nn的排列pp，找一个元素，使得从排列中取出这个元素以后排列的records最多。一个record是一个元素aiai满足：对于每个正整数 1≤j<i1≤j<i, ai>ajai>aj。

树状数组#

满足题述要求的元素等价于其是前缀数组中的最大值

用一个is_数组维护该值在原数组中是否为前缀最大值

维护树状数组，从左到右查询当前值的前面是否有大于他的数，如果等于0，则表明其是前缀最大值；如果等于1，则表明删去这个最大值后，该位置会变为前缀最大值，用一个数组维护因为删除前面的最大值而导致的该位置满足条件数的增加(过程维护前缀最大值，便于对其进行增加)

枚举删除的位置，删除后的满足体条件的数 =

原来的 records - 被删元素是否为 record + 删除后新增的 records 数量

1
class FenwickTree:
2
    def __init__(self, length):
3
        self.length = length
4
        self.tree = [0] * (length + 1)
5

6
    def lowbit(self, x):
7
        return x & -x
8

9
    def add(self, idx, val):
10
        while idx <= self.length:
11
            self.tree[idx] += val
12
            idx += self.lowbit(idx)
13

14
    def query(self, idx):
15
        res = 0
16
        while idx > 0:
17
            res += self.tree[idx]
18
            idx -= self.lowbit(idx)
19
        return res
20

21
def main():
22
    n = int(input())
23
    p = list(map(int,input().split()))
24

25
    is_ = [False]*n
26
    g = [0]*n
27
    mx = -1
28
    mx_idx = -1
29
    base = 0
30
    bit = FenwickTree(n)
31

32
    for i,x in enumerate(p):
33
        get = i - bit.query(x)
34
        if get == 0:
35
            is_[i] = True
36
            base += 1
37
        elif get == 1:
38
            g[mx_idx] += 1
39

40
        if x > mx:
41
            mx = x
42
            mx_idx = i
43

44
        bit.add(x,1)
45

46
    cur = -1
47
    ans = n+1
48
    for i in range(n):
49
        ggain = base - (1 if is_[i] else 0) + g[i]
50
        if ggain > cur or (ggain == cur and p[i] < ans):
51
            ans = p[i]
52
            cur = ggain
53
    print(ans)
54

55
if __name__ == "__main__":
56
    main()

[范围增加] + [单点查询]#

数组下标均从1开始；

对于a = [3,2,7,6,2,5]

其差分数组 b = [3,-1,5,-1,-4,3]

那么a[i] = b[1] + b[2] + ··· b[i-1] + b[i]

限制要在2~5位置上+3，add(2,5,3)

针对操作后的差分数组b=[3,2,5,-1,-4,0](在 $l$ 处+3 $,r+1$ 处 -3)

那么a[i] = b[1] + b[2] + ··· b[i-1] + b[i]

那么在树状数组中实现范围增加，只需要针对差分数组b：add(l,+3),add(r+1,-3)

实现单点查询即为求l的和

洛谷P3368#

题目#

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

将某区间每一个数加上 x；
求出某一个数的值。

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

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

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

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

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

树状数组#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
class FenwickTree {
5
    int n;
6
    vector<long long> tree;
7
public:
8
    FenwickTree(int n) : n(n), tree(n + 1, 0) {}
9

10
    void add(int idx, long long val) {
11
        for (; idx <= n; idx += idx & -idx) {
12
            tree[idx] += val;
13
        }
14
    }
15

16
    long long sum(int idx) {
17
        long long res = 0;
18
        for (; idx > 0; idx -= idx & -idx) {
19
            res += tree[idx];
20
        }
21
        return res;
22
    }
23
};
24

25
int main(){
26
    int n,m;
27
    cin>>n>>m;
28
    FenwickTree bit(n);
29
    int pre = 0;
30
    for(int i = 1;i <= n;i++){
31
        int cur;
32
        cin >> cur;
33
        bit.add(i,cur - pre);
34
        pre = cur;
35
    }
36

37
    while(m--){
38
        int op;
39
        cin >> op;
40
        if(op == 1){
41
            int x,y;
42
            cin >> x >> y;
43
            long long k;
44
            cin >> k;
45
            bit.add(x,k);
46
            bit.add(y+1,-k);
47
        }
48
        else{
49
            int x;
50
            cin >> x;
51
            cout << bit.sum(x) << endl;
52
        }
53
    }
54
    return 0;
55
}

[范围增加] + [范围查询]#

在[范围增加] + [单点查询]的基础上，对于范围查询query(l,r)

针对query(k)：原数组1~k的累加和 = $A_1 + A_2 + ··· +A_k$ = $D_1 + (D_1+ D_2) + ··· + (D_1 + D_2 + ··· + D_k)$

即： $k * \sum_{i=1}^{k} D_i - \sum_{i=1}^{k} (i-1)*D_i$

用两个树状数组分别维护这两个信息

Tree1 :

bit1.add(x, k);``bit1.add(y + 1, -k);

Tree2:

bit2.add(x, 1LL * x * k);``bit2.add(y + 1, -1LL * (y + 1) * k);

prefix(r) = (r+1) * sum(bit1, r) - sum(bit2, r)

洛谷P3372#

题目#

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

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

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

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

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

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

树状数组#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
class FenwickTree {
5
    long long n;
6
    vector<long long> tree;
7
public:
8
    FenwickTree(long long n) : n(n), tree(n + 1, 0) {}
9

10
    void add(long long idx, long long val) {
11
        for (; idx <= n; idx += idx & -idx) {
12
            tree[idx] += val;
13
        }
14
    }
15

16
    long long sum(long long idx) {
17
        long long res = 0;
18
        for (; idx > 0; idx -= idx & -idx) {
19
            res += tree[idx];
20
        }
21
        return res;
22
    }
23
};
24

25
int main() {
26
    ios::sync_with_stdio(false);
27
    cin.tie(0);
28

29
    long long n, m;
30
    cin >> n >> m;
31

32
    FenwickTree bit1(n);  // 维护 b[i]
33
    FenwickTree bit2(n);  // 维护 i * b[i]
34

35
    // 构建差分数组
36
    long long pre = 0;
37
    for (long long i = 1; i <= n; i++) {
38
        long long cur;
39
        cin >> cur;
40
        long long diff = cur - pre;  // b[i] = a[i] - a[i-1]
41

42
        bit1.add(i, diff);          // b[i] 加入 bit1
43
        bit2.add(i, 1LL * i * diff); // i * b[i] 加入 bit2
44

45
        pre = cur;
46
    }
47

48
    while (m--) {
49
        long long op;
50
        cin >> op;
51

52
        if (op == 1) {
53
            long long x, y;
54
            long long k;
55
            cin >> x >> y >> k;
56

57
            // bit1 更新：b[x] += k, b[y+1] -= k
58
            bit1.add(x, k);
59
            bit1.add(y + 1, -k);
60

61
            // bit2 更新：x*b[x] += x*k, (y+1)*b[y+1] -= (y+1)*k
62
            bit2.add(x, 1LL * x * k);
63
            bit2.add(y + 1, -1LL * (y + 1) * k);
64
        } else {
65
            long long x, y;
66
            cin >> x >> y;
67

68
            // prefix(r) = (r+1) * sum(bit1, r) - sum(bit2, r)
69
            auto prefix = [&](long long idx) -> long long {
70
                return 1LL * (idx + 1) * bit1.sum(idx) - bit2.sum(idx);
71
            };
72

73
            long long ans = prefix(y) - prefix(x - 1);
74
            cout << ans << '\n';
75
        }
76
    }
77

78
    return 0;
79
}

[逆序对]#

洛谷P1908#

题目#

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 ai>aj 且 i<j 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

第一行，一个数 n，表示序列中有 n 个数。

第二行 n 个数，表示给定的序列。序列中每个数字不超过 109。

输出序列中逆序对的数目。

归并排序#

1
def merge(a,l,r,tmp):
2
    if l >= r:
3
        return 0
4
    mid = (l + r)//2
5
    ans = merge(a,l,mid,tmp) + merge(a,mid+1,r,tmp)
6

7
    # 合并
8
    i,j,k = l,mid+1,l
9
    while i <= mid and j <= r:
10
        if a[i] <= a[j]:
11
            tmp[k] = a[i]
12
            i += 1
13
        else:
14
            ans += mid - i + 1
15
            tmp[k] = a[j]
16
            j += 1
17
        k += 1
18

19
    while i <= mid:
20
        tmp[k] = a[i]
21
        i += 1
22
        k += 1
23

24
    while j <= r:
25
        tmp[k] = a[j]
26
        j += 1
27
        k += 1
28

29
    for i in range(l,r+1):
30
        a[i] = tmp[i]
31

32
    return ans
33

34
def main():
35
    n = int(input())
36
    a = list(map(int,input().split()))
37
    tmp = [0]*n
38
    print(merge(a,0,n-1,tmp))
39

40
if __name__ == "__main__":
41
    main()

树状数组#

从后往前遍历

统计≤当前数-1的数的频率，并更新该数的词频

此频率可以通过树状数组long查询

对数组进行[离散化]

1
class FenwickTree:
2
    def __init__(self, length):
3
        self.length = length
4
        self.tree = [0] * (length + 1)
5

6
    def lowbit(self, x):
7
        return x & -x
8

9
    def update(self, idx, val):
10
        while idx <= self.length:
11
            self.tree[idx] += val
12
            idx += self.lowbit(idx)
13

14
    def query(self, idx):
15
        res = 0
16
        while idx > 0:
17
            res += self.tree[idx]
18
            idx -= self.lowbit(idx)
19
        return res
20

21
def main():
22
    n = int(input())
23
    a = list(map(int,input().split()))
24

25
    # 离散化
26
    a_sort = sorted(set(a))
27
    rank = {v: i + 1 for i,v in enumerate(a_sort)}
28
    bit = FenwickTree(n)
29
    ans = 0
30

31
    # 逆序遍历
32
    for i in range(n - 1,-1,-1):
33
        r = rank[a[i]]
34
        ans += bit.query(r - 1)
35
        bit.update(r,1)
36
    print((ans))
37

38
if __name__ == "__main__":
39
    main()

力扣493#

题目#

给定一个数组nums，如果i < j且nums[i] > 2*nums[j]我们就将(i, j)称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

树状数组#

与逆序对的唯一区别在于树状数组中加入的计数频数是2*a[i]

后续遍历查找≤当前值-1的频数

1
class FenwickTree:
2
    def __init__(self, length):
3
        self.length = length
4
        self.tree = [0] * (length + 1)
5

6
    def lowbit(self, x):
7
        return x & -x
8

9
    def update(self, idx, val):
10
        while idx <= self.length:
11
            self.tree[idx] += val
12
            idx += self.lowbit(idx)
13

14
    def query(self, idx):
15
        res = 0
16
        while idx > 0:
17
            res += self.tree[idx]
18
            idx -= self.lowbit(idx)
19
        return res
20

21

22
class Solution:
23
    def reversePairs(self, a: List[int]) -> int:
24
        n = len(a)
25
        b = []
26
        for x in a:
27
            b.append(x)
28
            b.append(2 * x)
29

30
        b_sort = sorted(set(b))
31
        rank = {v: i + 1 for i, v in enumerate(b_sort)}
32

33
        bit = FenwickTree(len(b_sort))
34
        ans = 0
35
        # 从右向左遍历
36
        for i in range(n - 1, -1, -1):
37
            # 查询已经访问过的2*a[j] < a[i] 的个数
38
            # 即查询排名 < rank[a[i]] 的所有元素
39
            ans += bit.query(rank[a[i]] - 1)
40

41
            # 将 2*a[i] 加入树状数组
42
            bit.update(rank[2 * a[i]], 1)
43

44
        return ans

MT3095树状数组+卢卡斯定理#

题目#

给定一个长为n的数字序列，现有m次操作，每一次操作一个区间[l,r]，使得区间反转，问操作后的数量逆序对的奇偶性

树状数组#

反转区间只改变内部的逆序对数量，不改变外部的逆序对

对于区间[l,r]，若其反转前有x个逆序对，反转后则有c(len,2) - x个逆序对

因此反转后的逆序对总数 = 原逆序对奇偶性^C(len,2)的奇偶性

(即相同为偶数0，相异为奇1)

原逆序对的奇偶性可以通过树状数组求解

C(len,2)的奇偶性取决于 n mod 4：

数学定理 Frobenius 定理 https://www.wolai.com/f1RVTvxPUeRLGmEYat76En#iJKcTVDFpEGJXSk2Rz97rv

卢卡斯定理：对于质数 p，C(n, k) mod p 等于 n 和 k 在 p 进制下逐位组合数的乘积。

当 p = 2 时：

C(n, k) 为奇数 ⇔ k 的二进制位是 n 的二进制位的子集（即 k & (n-k) == 0）
等价于 k & (n-k) == 0

对于 k = 2：

C(n, 2) 为奇数 ⇔ 2 & (n-2) == 0
即 n-2 的二进制最低位为 0 ⇔ n-2 是偶数 ⇔ n 是偶数
再进一步：n = 4k+2 或 4k+3 时成立

卢卡斯定理将大组合数模质数分解为小组合数逐位相乘，当 p=2 时，C(n,k) 为奇数当且仅当 k 的二进制位是 n 的二进制位的子集。

1
import sys
2

3
class FenwickTree:
4
    def __init__(self, length):
5
        self.length = length
6
        self.tree = [0] * (length + 1)
7

8
    def lowbit(self, x):
9
        return x & -x
10

11
    def update(self, idx, val):
12
        while idx <= self.length:
13
            self.tree[idx] += val
14
            idx += self.lowbit(idx)
15

16
    def query(self, idx):
17
        res = 0
18
        while idx > 0:
19
            res += self.tree[idx]
20
            idx -= self.lowbit(idx)
21
        return res
22

23

24
def get_parity(a):
25
    """返回逆序对数量的奇偶性：0 偶，1 奇"""
26
    n = len(a)
27
    a_sort = sorted(set(a))
28
    rank = {v: i + 1 for i, v in enumerate(a_sort)}
29
    bit = FenwickTree(n)
30
    ans = 0
31

32
    for i in range(n - 1, -1, -1):
33
        r = rank[a[i]]
34
        ans += bit.query(r - 1)
35
        bit.update(r, 1)
36

37
    return ans & 1
38

39

40
def main():
41
    input = sys.stdin.readline
42

43
    n = int(input())
44
    p = list(map(int, input().split()))
45

46
    parity = get_parity(p)
47

48
    m = int(input())
49
    for _ in range(m):
50
        l, r = map(int, input().split())
51
        length = r - l + 1
52

53
        # C(length, 2) 为奇数 ⇔ length % 4 == 2 或 3
54
        if length % 4 == 2 or length % 4 == 3:
55
            parity ^= 1
56

57
        print(parity)
58

59

60
if __name__ == "__main__":
61
    main()

[上升三元组的数量]#

洛谷P1637#

题目#

Erwin 最近对一种叫 thair 的东西巨感兴趣。。。

在含有 n 个整数的序列 a1,a2,…,an 中，三个数被称作thair当且仅当 i<j<k 且 ai<aj<ak。

求一个序列中 thair 的个数。

开始一行一个正整数 n,

以后一行 n 个整数 a1,a2,…,an。

一行一个整数表示 thair 的个数。

树状数组#

用两个数组数组维护

第一个树状数组表示枚举到位置i有多少个小于x

第二个树状数组表示枚举到位置i有多少个二元上升序列的第二个元素小于x

1
class FenwickTree:
2
    def __init__(self, length):
3
        self.length = length
4
        self.tree = [0] * (length + 1)
5

6
    def lowbit(self, x):
7
        return x & -x
8

9
    def add(self, idx, val):
10
        while idx <= self.length:
11
            self.tree[idx] += val
12
            idx += self.lowbit(idx)
13

14
    def query(self, idx):
15
        res = 0
16
        while idx > 0:
17
            res += self.tree[idx]
18
            idx -= self.lowbit(idx)
19
        return res
20

21
def main():
22
    n = int(input())
23
    a = list(map(int,input().split()))
24
    bit1 = FenwickTree(n)
25
    bit2 = FenwickTree(n)
26
    a_sort = sorted(a)
27
    rank = {v:i+1 for i,v in enumerate(a_sort)}
28
    ans = 0
29
    for i in range(n):
30
        r = rank[a[i]]
31
        # 查询当前结尾三元组的数量
32
        ans += bit2.query(r-1)
33
        # 更新以当前值做结尾升序一元组的数量
34
        bit1.add(r,1)
35
        # 更新以当前值做结尾升序二元组的数量
36
        bit2.add(r,bit1.query(r-1))
37
    print(ans)
38

39
if __name__ == "__main__":
40
    main()

[离线查询]#

洛谷P1972#

题目#

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。

有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

第一行一个正整数 n，表示项链长度。第二行 n 个正整数 ai，表示项链中第 i 个贝壳的种类。

第三行一个整数 m，表示 HH 询问的个数。接下来 m 行，每行两个整数 l,r，表示询问的区间。

离线查询#

记录每个查询，并将其按照左边界进行升序排序

用一个map记录每种贝壳最后出现的次数

顺序遍历排序后的查询，对于当前的[l,r]区间，用树状数组维护记录贝壳最后出现的位置；

对于每个数字，只在它最新出现的位置维护 1
当数字再次出现时，先移除旧位置的 1，再在新位置加 1
这样保证任意时刻，每个数字只被计数一次

1
// 记录颜色最后出现的位置
2
    unordered_map<int,int> last;
3
    // 离线查询
4
    int idx = 0;
5
    for(auto [l,r,qid] : q){
6
        while(idx < r){
7
            int x = a[idx];
8
            if(last.count(x)){
9
                bit.update(last[x],-1);
10
            }
11
            last[x] = idx + 1;
12
            bit.update(last[x],1);
13
            idx++;
14
        }
15
        ans[qid] = bit.query(r) - bit.query(l - 1);
16
    }

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
class FenwickTree {
5
private:
6
    int length;
7
    vector<int> tree;
8

9
    int lowbit(int x) {
10
        return x & -x;
11
    }
12

13
public:
14
    FenwickTree(int n) : length(n), tree(n + 1, 0) {}
15

16
    void update(int idx, int val) {
17
        while (idx <= length) {
18
            tree[idx] += val;
19
            idx += lowbit(idx);
20
        }
21
    }
22

23
    int query(int idx) {
24
        int res = 0;
25
        while (idx > 0) {
26
            res += tree[idx];
27
            idx -= lowbit(idx);
28
        }
29
        return res;
30
    }
31
};
32

33

34
int main(){
35
    int n;
36
    cin >> n;
37
    vector<int> a(n);
38
    for(int i = 0;i < n;i++){
39
        cin >> a[i];
40
    }
41

42
    int m;
43
    cin >> m;
44
    vector<tuple<int,int,int>> q;
45
    for(int i = 0;i < m;i++){
46
        int l,r;
47
        cin >> l >> r;
48
        q.push_back({l,r,i});
49
    }
50

51
    // 按照右端点排序
52
    sort(q.begin(), q.end(),
53
         [](const auto& x, const auto& y) {
54
             return get<1>(x) < get<1>(y);
55
         });
56

57
    FenwickTree bit(n);
58
    vector<int> ans(m);
59
    // 记录颜色最后出现的位置
60
    unordered_map<int,int> last;
61
    // 离线查询
62
    int idx = 0;
63
    for(auto [l,r,qid] : q){
64
        while(idx < r){
65
            int x = a[idx];
66
            if(last.count(x)){
67
                bit.update(last[x],-1);
68
            }
69
            last[x] = idx + 1;
70
            bit.update(last[x],1);
71
            idx++;
72
        }
73
        ans[qid] = bit.query(r) - bit.query(l - 1);
74
    }
75
    for(int i = 0;i < m;i++){
76
        cout << ans[i] << '\n';
77
    }
78

79
}

MT3066#

题目·偶数个数的异或和#

给定一个含有nn个数的序列A（A1,A2,A3……An）有m组询问。

每组询问的形式为x，y代表查询[x,y]区间（第x个数到第y个数）中出现次数为偶数的数的异或和,如果没有出现次数为偶数的数，输出0（比如区间中出现次数为偶数的数有3 7 8，那么3^7^8就是询问的结果）。

离线查询+异或#

设区间内每个数出现次数为 cnt[x]。

所有数的异或和 = ⊕_{x} (cnt[x] % 2 == 1 ? x : 0)
所有不同数的异或和 = ⊕_{x} x

出现偶数次的数的异或和 = ⊕_{x} (cnt[x] % 2 == 0 ? x : 0)

因为：所有不同数 = 奇数次的数 ∪ 偶数次的数

所以：偶数次的数异或 = 所有不同数异或 ⊕ 奇数次的数异或 = 所有不同数异或 ⊕ 所有数异或

1
import sys
2

3
class FenwickTree:
4
    def __init__(self, length):
5
        self.length = length
6
        self.tree = [0] * (length + 1)
7

8
    def lowbit(self, x):
9
        return x & -x
10

11
    def update(self, idx, val):
12
        while idx <= self.length:
13
            self.tree[idx] ^= val
14
            idx += self.lowbit(idx)
15

16
    def query(self, idx):
17
        res = 0
18
        while idx > 0:
19
            res ^= self.tree[idx]
20
            idx -= self.lowbit(idx)
21
        return res
22

23
    def range_xor(self, l, r):
24
        return self.query(r) ^ self.query(l - 1)
25

26

27
def main():
28
    input = sys.stdin.readline
29

30
    n = int(input())
31
    a = [0] + list(map(int, input().split()))
32

33
    m = int(input())
34
    q = []
35
    for i in range(m):
36
        x, y = map(int, input().split())
37
        q.append([x, y, i])
38

39
    # 按右端点排序
40
    q.sort(key=lambda q: q[1])
41

42
    # 前缀异或（区间所有数的异或和）
43
    pre_xor = [0] * (n + 1)
44
    for i in range(1, n + 1):
45
        pre_xor[i] = pre_xor[i - 1] ^ a[i]
46

47
    # 离线查询
48
    last = {}
49
    ans = [0]*m
50
    bit = FenwickTree(n)
51
    idx = 1
52
    for l,r,p in q:
53
        while idx <= r:
54
            x = a[idx]
55
            if x in last:
56
                bit.update(last[x],x)
57
            last[x] = idx
58
            bit.update(idx,x)
59
            idx += 1
60
        # 区间不同数的异或和
61
        distinct_xor = bit.range_xor(l, r)
62

63
        # 区间所有数的异或和
64
        all_xor = pre_xor[r] ^ pre_xor[l - 1]
65

66
        # 出现偶数次的数的异或 = 不同数异或 ^ 所有数异或
67
        ans[p] = distinct_xor ^ all_xor
68

69
    print('\n'.join(map(str, ans)))
70
if __name__ == "__main__":
71
    main()

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
class FenwickTree {
5
private:
6
    int n;
7
    vector<int> tree;
8

9
public:
10
    FenwickTree(int n) : n(n), tree(n + 1, 0) {}
11

12
    void update(int idx, int val) {
13
        while (idx <= n) {
14
            tree[idx] ^= val;
15
            idx += idx & -idx;
16
        }
17
    }
18

19
    int query(int idx) {
20
        int res = 0;
21
        while (idx > 0) {
22
            res ^= tree[idx];
23
            idx -= idx & -idx;
24
        }
25
        return res;
26
    }
27

28
    int range_xor(int l, int r) {
29
        return query(r) ^ query(l - 1);
30
    }
31
};
32

33
int main() {
34
    ios::sync_with_stdio(false);
35
    cin.tie(0);
36

37
    int n;
38
    cin >> n;
39

40
    vector<int> a(n + 1, 0);
41
    for (int i = 1; i <= n; i++) {
42
        cin >> a[i];
43
    }
44

45
    int m;
46
    cin >> m;
47

48
    // 存储查询：{l, r, idx}
49
    vector<array<int, 3>> queries;
50
    for (int i = 0; i < m; i++) {
51
        int l, r;
52
        cin >> l >> r;
53
        queries.push_back({l, r, i});
54
    }
55

56
    // 按右端点排序
57
    sort(queries.begin(), queries.end(), [](const array<int, 3>& A, const array<int, 3>& B) {
58
        return A[1] < B[1];
59
    });
60

61
    // 前缀异或（区间所有数的异或和）
62
    vector<int> pre_xor(n + 1, 0);
63
    for (int i = 1; i <= n; i++) {
64
        pre_xor[i] = pre_xor[i - 1] ^ a[i];
65
    }
66

67
    // 离线处理
68
    unordered_map<int, int> last;
69
    vector<int> ans(m, 0);
70
    FenwickTree bit(n);
71
    int idx = 1;
72

73
    for (auto &q : queries) {
74
        int l = q[0], r = q[1], qi = q[2];
75

76
        // 扩展右指针到 r
77
        while (idx <= r) {
78
            int x = a[idx];
79
            auto it = last.find(x);
80
            if (it != last.end()) {
81
                bit.update(it->second, x);  // 消除旧位置的贡献
82
            }
83
            last[x] = idx;
84
            bit.update(idx, x);             // 加入新位置
85
            idx++;
86
        }
87

88
        // 区间不同数的异或和
89
        int distinct_xor = bit.range_xor(l, r);
90

91
        // 区间所有数的异或和
92
        int all_xor = pre_xor[r] ^ pre_xor[l - 1];
93

94
        // 出现偶数次的数的异或 = 不同数异或 ^ 所有数异或
95
        ans[qi] = distinct_xor ^ all_xor;
96
    }
97

98
    for (int i = 0; i < m; i++) {
99
        cout << ans[i] << '\n';
100
    }
101

102
    return 0;
103
}

音乐

音乐

[算法专项] 树状数组

树状数组#

算法思想#

[单点修改] + [区间查询]#

区间查询#

单点修改#

模板-洛谷P3374#

问题描述#

树状数组#

洛谷P16799逆元+维护两个树状数组#

题目#

逆元+维护两个树状数组#

MT2142#

题目#

树状数组#

[范围增加] + [单点查询]#

洛谷P3368#

题目#

树状数组#

[范围增加] + [范围查询]#

洛谷P3372#

题目#

树状数组#

[逆序对]#

洛谷P1908#

题目#

归并排序#

树状数组#

力扣493#

题目#

树状数组#

MT3095树状数组+卢卡斯定理#

题目#

树状数组#

[上升三元组的数量]#

洛谷P1637#

题目#

树状数组#

[离线查询]#

洛谷P1972#

题目#

离线查询#

MT3066#

题目·偶数个数的异或和#

离线查询+异或#

文章分享

音乐

目录