夏令营7.28总结

树状数组

lowbit

正整数$x$的二进制写法里最右边（也就是最后）那个1被称为$x$的$\text{lowbit}$

$\text{lowbit}(x)$是能整数$x$的2的最高次方

计算方法：$x\text{&}-x$（最简洁）

int lowbit(int x){
    return x&(-x);
}

对于正整数$x,-x$的编码是把$x$的编码（即$x$的二进制写法）的每一位都取反再加一。

树状数组模板

构建方式

通过序列$A$算出树状数组$B$的方式：

• 方法1：根据定义：算出A的前缀和序列，记作$S$，那么$B_i=S_i-S_{i-\text{lowbit}(i)}$
• 方法2：假想一开始$A$的每一项都是0，而把$A_i$的初始值通过加操作加给$A_i$。

树状数组被叫做这个名字是因为他隐含着树的结构，所以才会怎么叫。

树状数组其实是树

$B_{i+\text{lowbit}(i)}$是包含$B_i$的最小元素，不妨把$B_{i+\text{lowbit}(i)}$看作$B_i$的父节点。

标展模板

int lowbit(int x){
    return x&(-x);
}


const int N=20;
int n;

int a[N];
int b[N];
int check(int x){
    int ans=0;
    while(x>0){
        ans+=b[x];
        x-=lowbit(x);
    }
    return ans;
}
void add(int x,int v){
    while(x<=n){
        b[x]+=v;
        x+=lowbit(x);
    }
    return;
}
int main(){
    return 0;
}

题目

动态前缀和问题

因为是模板题，所以把题面也放上来。

给你一个长为$N$的整数序列$A=(A_1,…,A_N)$。处理$Q$个操作。操作分为两种：

• 给你一个下标$i$，求$A_1+A_2+···+A_i$。
• 给你一个整数$x$和一个下标$i$，给$A_i$加上$x$。

思路：

考虑一个与序列$A$一样长的序列$B=(B_1,…,B_N)$。

对于每个$i=1,…,N$：$B_i=A_i+A_{i-1}+···+A_{i-\text{lowbit}(i)+1}$

也就是说$B_i$是从$A_i$开始往左数$\text{lowbit}(i)$项之和。

用一张图片辅助理解。

动态区间和问题

区间和可以表示为两个前缀和的差，有
$$
A_l+···+A_r=(A_1+···+A_r)-(A_1+···+A_{l-1}).
$$

T1

考虑序列$A$的差分序列$D=(D_1,…,D_N)$，其中$D_1=A_1,D_i=A_i-A{i-1}$（$2\le i\le N$）。不难看出，对于每个$i=1,…,N$，有$A_i=D_1+···+D_i$

树状数组通过二进制分解的思想，将数组划分为若干个子区间，每个节点负责维护一个子区间的和。其核心操作依赖于lowbit函数，该函数用于找到一个数二进制表示中最低位的1所对应的值（如lowbit(6)=2，因为6的二进制是110，最低位1对应$2^1=2$）。

• 单点更新：当更新位置x时，通过lowbit找到所有包含x的节点，依次更新这些节点的值。
• 前缀和查询：当查询前x个元素的和时，通过lowbit分解x，累加所有相关节点的值。

T2

其实树状数组都比较模板化，导致没什么好讲的

• 单点更新：更新位置x时，通过lowbit找到所有包含x的节点，依次更新这些节点的值。
• 前缀和查询：查询前x个元素的和时，通过lowbit分解x，累加所有相关节点的值。
• 区间和计算：利用前缀和的差实现，即区间[l, r)的和$=$前r个元素的和$-$前l个元素的和。

T3

这题还用到了差分的思想，所以可以讲的详细一点。

对于区间更新（给$[l,r]$内所有元素加$x$），传统方法需要遍历区间内所有元素，时间复杂度为$O(r-l+1)$。而差分思想通过以下方式优化：

• 定义一个差分数组$d$，其中$d[i]$表示数组$a$中第$i$个元素与第$i-1$个元素的差值（$d[1]=a[1]$，$d[i]=a[i]-a[i-1]$）。
• 给$[l,r]$加$x$时，只需更新差分数组：$d[l]+=x$，$d[r+1]-=x$（若$r+1\le n$）。
• 数组$a[i]$的值可通过差分数组的前缀和计算：$a[i]=前缀和(d[1..i])$。

T4

这题能讲的也挺多。

1. 离散化处理

由于序列元素可能很大（如超出树状数组的索引范围），但逆序对只与元素的相对大小有关，因此需要先对元素进行离散化：

• 将原始序列的元素按大小排序，赋予每个元素一个 “排名”（相同元素按原位置先后排序）。
• 离散化后，元素的排名范围为1到$n$，可直接作为树状数组的索引，避免空间浪费。

2. 树状数组统计逆序对

逆序对的统计采用 “从左到右遍历，记录已出现元素” 的策略：

• 遍历序列时，对于当前元素$a[i]$，其逆序对数量等于 “已遍历元素中比$a[i]$大的元素个数”。
• 树状数组用于记录已遍历元素的出现次数，通过前缀和查询可快速计算 “已出现的、排名小于等于当前元素排名的元素个数”，进而推出 “比当前元素大的元素个数”。

T5

这题是树状数组与二进制搜索结合。

1. 树状数组维护前缀和

树状数组的经典功能是快速计算前缀和与执行单点更新：

• 单点更新（add函数）：给位置$i$的元素增加$x$，通过树状数组的索引跳转（$i+=i\text{&}-i$）更新相关节点。
• 前缀和查询（sum 函数）：计算从位置0到$i$的元素总和，通过索引跳转（$i-=i\text{&}-i$）累加相关节点的值。

2. 二进制搜索寻找下界

为了找到前缀和大于等于$x$的最小索引，采用二进制跳跃：

• 从高位到低位（这里我们从$2^{19}$开始）尝试跳跃，判断累加当前区间的和后是否仍小于$x$。
• 若仍小于$x$，则纳入该区间并继续尝试更大的跳跃；否则缩小跳跃范围。
• 最终得到的位置加1即为满足条件的最小索引。

关于在考场上的方法（考场上什么做）

在考试的时候，前两题基本上可以放心大胆地直接去做（Just do it），在遇到难题的时候，不要一下子开始埋头苦做，一做一个不吱声。要

• 浏览一下这题以及后面题目的大致难度，评估自己最适合的题目
• 如果确定以及是最适合自己的题目，但是还是认为超出了自己的能力范围，那么就可以考虑一下观察数据范围，分组的数据的强度。有些题目还会有特殊性质，比如出现一些可以让暴力过的部分分。那么这时候，就要评估自己的水平，能实现那一组的部分分。这样，可以防止爆0.

有些题目，比如去年的T3，只给了一个小样例，但是你认为自己的程序还需要更多的测试，那么这时候就可以考虑一下使用对拍+Windows批处理脚本自动比对是否正确。

自动对拍

@echo off
:go
make_data.exe >in.txt
need_test.exe < in.txt > out1.txt
ok.exe < in.txt > out2.txt
fc out1.txt out2.txt
if not errorlevel 1 goto go
echo 找到一组错误解
goto go

这段代码的中，make_data.exe是用于生成数据的程序，need_test.exe是待测试的正解，ok.exe是确保了正确性的暴力程序。脚本会用数据生成器生成一组数据，并分别给待测程序和暴力程序测试，比对输出结果。如果相同，就会再试一次，不同就会自动停止，保留错误的那组测试数据。

使用方法就是把这段脚本保存到一个.bat的批处理文件中。

准备好之后，只要让他在后台自动运行就可以了。过一段时间，再来看是否正确。