8
UPDATE: 决定把这个做成较为详细的笔记
UPDATE: 骗你的，做不下去了，只做了树状数组
排版很乱，见谅哈。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1.树状数组（BINARY INDEXED TREE,BIT,二叉索引树）
简介：可以处理区间修改，查询区间和/差等问题（仅支持前缀可减的操作）。
问题：给出一个数组 {an}\{a_n\}{an }，请在 logn\log{n}logn 的时间复杂度内执行区间修改或区间查询操作。
关于树状数组，我们从一个很聪明的函数讲起：
lowbit(x)=x&(−x)\tt{lowbit(x)=x\&(-x)}lowbit(x)=x&(−x)
指 xxx 与 −x-x−x 按位与的结果。
可以发现，当 xxx 是奇数时，lowbit(x)=1\tt{lowbit(x)=1}lowbit(x)=1，反之 lowbit(x)=\tt{lowbit(x)}=lowbit(x)= 二进制下的 xxx 从左往右出现的最后一个 111 及其后面的 000 组成的数的十进制。这么听着有点绕，例如 lowbit(6)\tt{lowbit(6)}lowbit(6)，(6)10=(110)2,(6)_{10}=(110)_2,(6)10 =(110)2 , 取 101010，得 (10)2=2(10)_2=2(10)2 =2，所以
lowbit(6)=2\tt{lowbit(6)=2}lowbit(6)=2。当然这个只是铺垫后面的内容，听不懂也没关系。你只需要知道 lowbit(x)\tt{lowbit(x)}lowbit(x) 的值一定是 222 的幂次，前提 x≠0x\ne 0x=0。
关键在于我们按 lowbit(x)\tt{lowbit(x)}lowbit(x) 的值将每个数分层并连边，居然神奇的出现了一棵二叉树！（如下图）
这棵二叉树非常神奇，对于节点 iii，如果他是左子结点，他的父节点为 i+lowbit(i)\tt{i+lowbit(i)}i+lowbit(i)，否则他的父节点为 i−lowbit(i)\tt{i-lowbit(i)}i−lowbit(i)。因此我们可以利用 lowbit\tt{lowbit}lowbit，对区间段进行前缀和计算。
构造一个辅助数组 c[]c[]c[]，定义 cic_ici 为覆盖节点 iii 及其左子树的区间和，即：
ci=∑i−lowbit(i)+1iaic_i=\sum_{i-lowbit(i)+1}^i a_i ci =i−lowbit(i)+1∑i ai
这时我们回归问题。
修改
观察 cic_ici 的定义，修改一个节点的值，只需要同步修改在其右上方的祖先的值即可。
查询
只需要将所有其左上方的祖先及其本身的值即可。
对于区间修改问题，由于 query\tt{query}query 本质上是前缀和，所以差分一下即可（换句话说，区间修改问题必须有可差分性）
模板题，上模板。
例题：
* 股票
提醒各位初学者，本题虽然不必离散化，但是你拿 aia_iai 建的树状数组就需要注意阈值上限是 maxai\max a_imaxai 不是 nnn 了。可能你们会觉得这句话很糖。
* 逆序对
由于 aia_iai 达到了 10910^9109，我们无法直接按照 aia_iai 的值建树状数组，因此考虑离散化：
* 1.复制 aaa 数组存入 ttt，将 ttt 排序。
* 2.将 ttt 用 unique\tt{unique}unique 函数去重。
* 3.用二分找原 aia_iai 在 ttt 中的位置。
这样我们就得到了 aia_iai 的相对大小顺序，把值域缩到了 5×1055\times 10^55×105 之内，可以建树状数组了。
2.线段树/(LAZY_TAG)
没写完。
3.权值线段树
洛谷我没找到板（没有给权值线段树の标签），自己放一个草题。
题目描述
给出 n,{an}n,\{a_n\}n,{an }，约定 b1=a1b_1=a_1b1 =a1 。对于 2≤i≤n2\le i \le n2≤i≤n：
bi=minj=1i−1∣aj−ai∣ b_i=\min_{j=1}^{i-1}|a_j-a_i| bi =j=1mini−1 ∣aj −ai ∣
求出 {bn}\{b_n\}{bn }。
输入
给出 n,{an}n,\{a_n\}n,{an }
输出
{bn}\{b_n\}{bn }
输入 111
输出 111
1≤n≤105,1≤ai≤1071\le n \le 10^5,1\le a_i\le 10^71≤n≤105,1≤ai ≤107 无需离散化&动态开点
Code:\tt{Code:}Code:
回转寿司,luogu5459,绿
九转大肠有没有食欲
发现与区间和有关，套上前缀和 sumsumsum。
考虑列不等式 L≤sumr−suml−1≤RL\le sum_r-sum_{l-1}\le RL≤sumr −suml−1 ≤R，直接维护这个是 n2n^2n2 的肯定不现实。
考虑变换得 sumr−R≤suml−1≤sumr−L(l<i)sum_r-R\le sum_l-1\le sum_r-L(l<i)sumr −R≤suml −1≤sumr −L(l<i)，考虑枚举 sumisum_isumi ，那么我们只要找出满足条件的 suml−1sum_{l-1}suml−1 的数量，就是对于 sumisum_isumi 的选择。
于是我们使用权值线段树维护 sumsumsum 的值，也就是要计算的 [sumi−R,sumi−L][sum_i-R,sum_i-L][sumi −R,sumi −L]，那把小于 iii 的 sumjsum_jsumj 全部丢进权值线段树即可。
需要注意的是，本题阈值很大，记得动态开点处理。
有帮助，赞一个