是鬼畜数据结构专题～

我是不会告诉你我打前两次NOIP/CSP的时候对这些东西都一无所知的（雾）。

这些有（du）趣（liu）的数据结构题往往伴随着各种鬼畜操作，各种诡异询问。毕竟裸的板子题越来越少了（哭），还是应该灵活运用。

分 块

蛮好打的数据结构，算是里面比较不毒瘤一点的了，理解也不难，下面稍微讲解一下他的思想。

基本思想？

有一区间长为 $n$ ，我们把他分成 $\sqrt{n}$ 个块，那由此一来每个块里就有 $n\div \sqrt{n}=\sqrt{n}$ 个数（倘若不能整分，就在末尾保留一个元素个数不满 $\sqrt{n}$ 的零头块），在处理过程中我们遵循“多块拆分处理，整块直接处理，零块暴力处理”的策略，以区间修改为例，我们先来体味一下这句话的意思。

我们把整条序列比作一个国家，分出的几个块比作城市，进行的修改比作 $\color{red}\colorbox{white}{政策}$ （zzmg警告）。

给出政策实行的范围在 $l,r$ 之间，要在这个范围里实施“羟基计划”（草）。我们想采用分块，怎么做？

下面三层情况：

$Case 1:$不多不少的一块，即这个政策正好坐落在一个城市上（惨 城市 惨），对于城市里的每个学生，我们不用一个一个告知“羟基计划”实行了。我们只要在政府网上发个公告，也就是在块上打个 $tag$ ，修改整块的有关信息（比如 $sum$ ），表示这个块里的元素被修改了，这样我们就不用把这一政策下放到个人，有效地减小了复杂度。

$Case 2:$国家打算对一个城市的部分人实施这一政策（\jk），那我们发公告的法子就行不通了（有误伤可能）。怎么搞，暴力即可，封顶 $\sqrt{n}$ 的工作量我们还承受不了嘛？直接告诉个人，你被选入了“羟基计划”（\kel）。我们甚至还可以再贪一把，如果政策在这个城市的受众面实在太广（指修改的元素多于 $\dfrac{\sqrt{n}}{2}$ ），也可以用发公告公布政策的施行方法，再悄悄告诉那些实则不参加计划的学生，他们是破格生（\fad）。比如先在块的总和上加上（参与羟基计划的人数* 1）， $tag+1$ ，再对那些其实不用加的元素暴力 $-1$ 。

$Case 3:$国家打算大面积施行“羟基计划”（危）。范围包含许多连续的”试点城市“和许多不在“试点城市”的“试点人”（自己编的）。怎么搞？我们已经知道了对单城市和城市内个人的操作套路，那我们把这个长区间拆分成一些整块和一些零块，对于这些东西分别按 $Case 1,2$ 的套路处理即可。

实现？好写即正义！

一些细节需要稍加注意：

  1. 可以预处理一下每一个程序位于哪一块内，以及每个块的左右界。我们以一道单点修改、区间查询最大值的题为例，实现如下（这里的处理方法还是挺值得玩味的，可以用特殊值帮助记忆？）：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    void pre()
    {
    	sqr=sqrt(n);
    	m=n/sqr;
    	for(int i=1;i<=n;i++)
    	{
    		block[i]=(i-1)/sqr+1;//预处理所在块
    		if(num[maxx[block[i]]]<num[i])
    		maxx[block[i]]=i;//预处理MAX
    	}
    	for(int i=1;i<=m;i++)
    	{
    		L[i]=(i-1)*sqr+1;
    		R[i]=i*sqr;//预处理左右界
    	}
    	
    	if(n%sqr)
    	{
    		L[m+1]=R[m]+1;
    		R[m+1]=n;//预处理最后的零头块上下界
    	}
    }
  2. 珂以定义两种 $\operatorname{check}$ 函数，(1)对应块内个体处理（$Case 2$），(2)对应全部处理（$Case 3$），(2)在运行中会调用(1)来处理他分出的散块情况。 $\operatorname{check}$ 也是如此。这里放一份区间加的部分代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    void update_2(int l,int r,int v)//Case 2
    {
         if((r-l+1)>(R[block[l]]-L[block[l]]+1)>>1)
         {//超过一半就处理另外一半，贪一把
              for (int i = L[block[l]]; i < l;i++)
              {
                   num[i] -= v;
              }
              for (int i = R[block[r]]; i > r;i--)
              {
                   num[i] -= v;
              }//告知另外一半破格生
         }
         else
         {
              for (int i = l; i <= r;i++)
              {
                   num[i] += v;//告知计划内的人
              }
         }
         sum[block[l]] += v * (r - l + 1);
         //发公告
    }
    void update_1(int l,int r,int v)
    {
         if(block[l]==block[r])
         {
              update_2(l, r, v);
         }/检测到Case 2，块内处理
         
         else//Case 3
         {
              update_2(l, R[block[l]], v);
              update_2(L[block[r]], r, v);
              //边角部分采用Case 2策略
              for (int i = block[l] + 1; i < block[r];i++)
              {
                   tag[i] += v;
                   sum[i] += v * (R[i] - L[i] + 1);
                   //发公告
              }
              //整块部分采用Case 1策略
         }
    }
  3. 数据结构的题目还是尽量多写函数，否则会 很 难 调！！！（血的教训） 。

这里放一份分块经典代码，主函数部分还是诸位视题目而写～

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6 + 7;
const int MAXN = 1e3 + 7;
#define int long long
int L[MAXN], R[MAXN], sum[MAXN], tag[MAXN];
int block[MAX], num[MAX];
int n, m, M, sqr;
int mode;
void pre()
{
     sqr = sqrt(n);
     m = n / sqr;
     for (int i = 1; i <= n; i++)
     {
          block[i] = (i - 1) / sqr + 1;
          sum[block[i]] += num[i];
     }
     for (int i = 1; i <= m; i++)
     {
          L[i] = (i - 1) * sqr + 1;
          R[i] = i * sqr;
     }

     if (n % sqr)
     {
          L[m + 1] = R[m] + 1;
          R[m + 1] = n;
     }
}
int check_2(int l, int r)
{
     int res = 0;
     if ((r - l + 1) > ((R[block[l]] - L[block[l]] + 1) >> 1))
     {
          res = sum[block[l]];
          for (int i = L[block[l]]; i < l; i++)
               res -= num[i] + tag[block[i]];
          for (int i = r + 1; i <= R[block[l]]; i++)
               res -= num[i] + tag[block[i]];
     }
     else
     {
          for (int i = l; i <= r; i++)
          {
               res += num[i] + tag[block[i]];
          }
     }
     return res;
}
int check(int l, int r)
{
     int res = 0;
     if (block[l] == block[r])
     {
          res = check_2(l, r);
     }
     else
     {
          res += check_2(l, R[block[l]]);
          res += check_2(L[block[r]], r);
          for (int i = block[l] + 1; i < block[r]; i++)
          {
               res += sum[i];
          }
     }
     return res;
}
void update_2(int l, int r, int v)
{
     if ((r - l + 1) > (R[block[l]] - L[block[l]] + 1) >> 1)
     {
          for (int i = L[block[l]]; i < l; i++)
          {
               num[i] -= v;
          }
          for (int i = R[block[l]]; i > r; i--)
          {
               num[i] -= v;
          }
          tag[block[l]] += v;
     }
     else
     {
          for (int i = l; i <= r; i++)
          {
               num[i] += v;
          }
     }
     sum[block[l]] += v * (r - l + 1);
}
void update_1(int l, int r, int v)
{
     if (block[l] == block[r])
     {
          update_2(l, r, v);
     }
     else
     {
          update_2(l, R[block[l]], v);
          update_2(L[block[r]], r, v);
          for (int i = block[l] + 1; i < block[r]; i++)
          {
               tag[i] += v;
               sum[i] += v * (R[i] - L[i] + 1);
          }
     }
}
signed main()
{
  
  return 0;
}

树 状 数 组

极其好打又极其难懂的数据结构，能解决绝大部分的单点修改、区间查询的题目，但是在笔者理解不能的年代，这东西是真的噩梦。所以笔者这里尽量描述得易于理解～（说句闲话：据不可靠消息，在某次浴谷网校的课上，当一位学生提问树状数组的原理是，LXL当场谔谔）

令人谔谔的思想

我们树状数组运用的思想主要是前缀和的思想，数组如其名，其结构层次就像一棵树，节点保存的都是一个区间的前缀和。就像下面这样：

这是一个树状数组保存值的方式，发现了吗， $A$ 数组里保存的值往往都是一个部分的值，这也就是他能做到高效区间求和（往往是 $\log{N}$ 级别）的奥秘。看上去就像一场不太公平的比赛？（雾）

我们干脆拿这种有保送资格的 公 平 竞 争 来举例子。

诡异的存储方式必然带来了诡异的操作方法，如何得知一个选手晋级后要参加的下场比赛成了处理的一大问题，我们来康康图上。

以 $1$ 为例，他从 $1$ 出发，下一场比赛在 $2$ 号位置，两个位置相差 $1$ 。再从 $2$ 出发，下一场比赛在 $4$ ，两个位置相差 $2$ 。再到 $8$ ，走 $4$ 步。$1$ 走一步， $2$ 走两步，$4$ 走四步？很难找出规律。

考虑从构建树状数组的方法入手吧， $1$ 所表示的区间位于赛程树的第一层， $3$ 表示的区间也在第一层，还有 $5$ 和 $7$ ，他们的下一场比赛都是在下一个位置。他们有什么共同特点，没错，都是奇数。奇数在二进制下表现的通性是什么？没错，表示 $2^0$ 的那一位上都是 $1$ 。

或许我们已经看出一点端倪了，同样的， $2$ 和 $6$ 位于赛程树的第二层，他们的下一场比赛在 $2$ 步之后， $2$ 和 $6$ 的二进制有什么特性?没错，表示 $2^0$ 的一位上是 $0$ ，但表示 $2^1$ 的一位上是 $1$ 。

我知道了（，但你出言不逊是）！下一场比赛与当前的距离，就是当前位置编号在二进制下，最靠后的不是 $0$ 的位置所表示 $2$ 的次幂值！那我们就有了这样的图：

（字有点小？）

怎么快速得到这个距离？有一个奇技淫巧或许是一种方法。

$\operatorname {lowbit}(a)=a\And-a$ 。这样可以取到 $a$ 最靠后的非 $0$ 位（为什么？好像有用到计算机补码的知识，笔者初赛从来都是挨打，我不会）。

知道了每名选手要打什么比赛，我们现在要对选手实力进行调整了，调整了一个选手的实力，必然会对他之后要打的比赛的格局产生影响（也就是改变了其它包含他的区间的值），所以我们要进行 $\log{N}$ 的单点修改（别觉得亏，为了区间查询的效率，这里的复杂度还是值得牺牲的），也就是修改所有他要打的比赛。具体做法就是从修改点 $pos$ 往上跳 $\operatorname{lowbit}$ ，直到 $pos \geq N$ 。

1
2
3
4
5
6
7
8
void update(int x, int k)
{
     while (x <= N)
     {
          tree[x] += k;//修改比赛格局
          x += lowbit(x);//跳lowbit
     }
}

接下来才是树状数组的绝妙之处—— $\log{N}$ 区间查询，其实理解了前缀和的思想就很容易了，无非是 $r$ 的前缀和减上 $l-1$ 的前缀和。单点前缀和在树状数组上怎么求？其实是单点修改的反向，从 $pos$ 往下跳 $\operatorname{lowbit}$ ，直到 $pos \leq 0$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int query(int x)
{
     int res = 0;
     while (x > 0)
     {
          res += tree[x];//总和加上这个位置表达的前缀和
          x -= lowbit(x);//跳lowbit
     }
     return res;
}
/*然后主函数里调用时是这样的*/

if (s == "Query")
{
    int fr = read();
    int to = read();
    cout << query(to) - query(fr - 1) << endl;
    //前缀和传统艺能
}

希望加深记忆的读者也可以在树状数组上跑一跑，模拟一下，康康是不是这么回事。

有一说一，这代码真的好打

下面是一道单点修改，区间求和的板子题代码～

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200007;
int N, M, tree[MAX];
int lowbit(int x)
{
     return x & (-x);
}
void update(int x, int k)
{
     while (x <= N)
     {
          tree[x] += k;
          x += lowbit(x);
     }
}
int query(int x)
{
     int res = 0;
     while (x > 0)
     {
          res += tree[x];
          x -= lowbit(x);
     }
     return res;
}
int read()
{
     int bj = 0, num = 0;
     char ch = getchar();
     while (!isdigit(ch))
     {
          if (ch == '-')
          {
               bj = 1;
          }
          ch = getchar();
     }
     while (isdigit(ch))
     {
          num = num * 10 + ch - '0';
          ch = getchar();
     }
     return bj ? -num : num;
}
int main()
{
     int T = read();
     for (int j = 1; j <= T; j++)
     {
          memset(tree, 0, sizeof(tree));
          N = read();
          for (int i = 1; i <= N; i++)
          {
               int num = read();
               update(i, num);
          }
          string s;
          cout << "Case " << j << ":" << endl;
          while (cin >> s && s != "End")
          {
               if (s == "Add")
               {
                    int p = read();
                    int num = read();
                    update(p, num);
               }
               if (s == "Sub")
               {
                    int p = read();
                    int num = read();
                    update(p, -num);
               }
               if (s == "Query")
               {
                    int fr = read();
                    int to = read();
                    cout << query(to) - query(fr - 1) << endl;
               }
          }
     }
}

三 $\operatorname{while}$ 怒切绿/蓝/紫题。

线 段 树

极其难打且难调的数据结构，但是可以处理的操作和询问却极其广泛（毕竟能力越大，责任越大）。思想是不难的，起码比树状数组简单（确信）。

就这思想

还是那样，我们依旧拿“羟基计划”来说事。（zzmg警告）

线段树，结构如其名，像树一样。对于他内部的存储方式，向来百家争鸣。我们可以理解为构建各级机构的过程。笔者在这里推出一种最为风靡且作者本人认为最优的的建树方式：

建树方法：结构体指针配合位运算装B法：

先把图上了！

这里的 $\mathtt{number}$ 数组是我们要存的值们，也就是对各人的“羟基计划”的各种方案。 $\mathtt{tree}$ 是我们最终建好的庞大的官僚体系 （八月肃反名单警告）。这里很容易看出，线段树是一个以空间换时间的典型数据结构。

体系上，每一个叶子节点都是针对于一个人的方案，每一个非叶子节点都是一个官员，负责一个区间。我们规定一个官员结点 $x$ 管辖的两个儿子（儿子可能是个人，也可能是另一个官员），他们所在的地址分别位于 $\mathtt{tree}$ 数组的 $2x$ 与 $2x+1$ ，用位运算装波小b，就是 $x<<1$ 和 $x<<1|1$ 。（据说是会快的）

我们这样来表示一些变量，一个结点有关的值有：$ls$：左儿子的编号， $rs$：右儿子的编号， $val$ ：值（“羟基计划”的方案）。

在实现上，我们采用递归二分的思想，往函数里传一个左边界 $l$ ，一个右边界 $r$ 。每次，我们把这个边界圈出的范围分成两半，对分出的两部分，分别进行递归，继续收缩范围。

还是那句话，递归的终点一定得要设置。如果左右边界合一，很明显，我们把范围收紧到了一格的位置，也就是收缩到了叶子节点上，他属于个人，直接赋值，直接向他告知“羟基计划”，然后 $return$ 走人。

这一部分实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

inline int ls(int x)
{
	return x<<1;	
}
inline int rs(int x)
{
	return x<<1|1;
}
//左右儿子
inline void build(ll now,ll l,ll r)//建树
//参数分别为根，左边界，右边界
{
	/*这里可以放一些tag的初始化，现在用不上*/
	if(l==r)
	{//叶子节点，赋值走人
		val[now]=num[l];	
		return;
	 } 
	int mdl=(l+r)>>1;//二分
	build(ls(now),l,mdl);
	build(rs(now),mdl+1,r);
    //分别处理左右两半部分
    /*这里可以放一些整合子节点信息的操作*/
	/*我们叫他push_up*/
}

$\operatorname{push}$_$\operatorname{up}$ 是我们整合一个结点俩儿子的信息的操作，也就是官员下访群众收集信息的操作。比如我们要求区间和，我们的 $\operatorname{push}$ _ $\operatorname{up}$ 就是使目前的 $now$ 结点的 $val$ 值等于两个子节点的 $val$ 之和。如下：

1
2
3
4
5
6
7

void update(int pos) 
{
	val[pos] = (val[ls(pos)] + val[rs(pos)]);
    //整合信息
    return;
}

我们为什么要专门把他放在一个函数里？因为我们之后的操作里还要用到（伏笔～）。

这样建树的优势：建树较有序，使其常数更小（或许？），子结点位置不固定，方便一些操作。

区间修改：一劳永逸懒标记下传法：

先谈思想，举个例子，我们要让 1～4 之间的所有人参加“羟基计划”。

我们从根结点（中央JY部） 开始更新，往下走。

树上，JY部有两个子机构，XX省JY厅(1)分管 $1$~$4$，XX省JY厅(2)分管 $5$~$6$ ，我们要修改的区间是 $1$~$4$ ，只只位于 XX省JY厅(1)的管辖范围（即发布“羟基计划”只是厅(1)的任务），所以我们往 XX省JY厅(1)的方向往下走。

XX省JY厅(1)有两个下属， XX市JY局(1)分管 $1$~$2$ ， XX市JY局(2)分管$3$~$4$ 。“羟基计划”与省里每个人都有关系，还记得我们分块的时候对于这种情况是如何操作的嘛？是了，发公告。如果一个部门的管辖区间被我们要修改的目标区间完全包含，我们直接在表示这个管辖区间的非叶子节点（也就是官员结点）上打 $tag$ ，如果还有什么这个管辖区间有关的值，比如 $sum$ 、$max$ ，也一并修改。我们这里就在XX省JY厅(1)上打上标记

那这样被修改的官员结点下属里别的官员呢，比如这里的 XX市JY局(1)和XX市JY局(2) ，我们要进行标记下传的操作了。通俗点说，就是让下面的局(1)局(2) 也得到这个公告。

我们标记下传的这个操作在里面叫做 $\operatorname{push}$_$\operatorname{down}$ ，实现是这样的：

（提醒：以下的 $sum$ 就是我们之前看到的那个 $val$ ，后面的代码同）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline void work(int x,int lft,int rgt,int tg)
{
	tag[x]+=tg;
    //tag的传递这样实现
	sum[x]+=tg*(rgt-lft+1);
    //这里以sum为例，是“这个管辖区间有关的值的修改”的一个例证
}
inline void push_down(int x,int lft,int rgt)
{
	int mdl=(lft+rgt)>>1;//二分
	work(ls(x),lft,mdl,tag[x]);
	work(rs(x),mdl+1,rgt,tag[x]);
    //对两部分进行tag的传递工作
	tag[x]=0;
    //清空这里的标记，毕竟已经传达给下属了，这里的公告可以销毁了
}

修改的全过程只有下传是不够的，我们修改了 $1$~$4$ ，那 $1$~$6$ 这个结点怎么办，很显然，我们需要让 $1$~$6$ 这个结点再次整合他下属的信息，整合信息的做法我记得我们之前提到过，就是所谓的 $\operatorname{push}$_$\operatorname{up}$ （伏笔消除！）。所以，一个区间修改就是下面这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline void change(int needl,int needr,int lft,int rgt,int x,int tg)
//参数特别说明：needl是我们要修改的区间，是不会变的。
//lft是我们递归到的左边界，会变。（r同理）
{
	if(needl<=lft&&needr>=rgt) 
	{
    //完全包含时的有关处理
		tag[x]+=tg;
		sum[x]+=tg*(rgt-lft+1);
		return;
	}
	push_down(x,lft,rgt);
    //标记下传
	int mdl=(lft+rgt)>>1;
	if(needl<=mdl) change(needl,needr,lft,mdl,ls(x),tg);
	if(needr>mdl) change(needl,needr,mdl+1,rgt,rs(x),tg);
    //二分递归，这里要判断这个羟基计划和这个下属到底有没有关系
    //就和一开始我们不走XX省JY厅(2)是一个道理
	push_up(x);
    //整合信息
}

（说句闲话：线段树是有一个公告向下属传达的过程的，而分块直接就是发公告，让下面人自己去看，可见线段树国的官员比分块国负责任）

区间查询：层层递归包括即返回法：

笔者个人觉得线段树的区间查询和区间修改还是蛮像的，大体说一下流程：

上级要检查 $4$~$5$ 的“羟基计划”实行情况。

假设我们之前已经在代表 $1$~$4$ 的官员结点上打了一个 $+1\ tag$ 。

老规矩，如果当前官员结点的管辖区间被完全包含，直接返回，比如我们要求一段区间的 $sum$ ，我们这个时候就应该返回被包含的管辖区间的总 $sum$ 。

我们之前有过很多区间修改的操作，往下走的路其实百废待兴，留了一些 $tag$ 。所以，还是要标记下传，为领导的检查开辟好道路（雾）。

二分我们的目标区间，递归这一操作，每次更新答案，比如我们要求一段区间的 $max$ ，这个时候 $ans$ 就可以等于

应该很好理解的叭（心虚）……

上个代码品品（区间求和）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline int check(int needl,int needr,int lft,int rgt,int x)
{
	int answer=0;//答案
	if(needl<=lft&&needr>=rgt)
	{
		return sum[x];//被包含，返回对应区间的sum
	}	
	push_down(x,lft,rgt);
    //标记下传
    int mdl=(lft+rgt)>>1;
	if(needl<=mdl) answer+=check(needl,needr,lft,mdl,ls(x));
	if(needr>mdl) answer+=check(needl,needr,mdl+1,rgt,rs(x));
    //二分递归
	return answer;
}

就这实现：

放一下板子题（线段树1） ，要求区间修改，区间求和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[500005], sum[500001], tag[500001];
int ls(int x)
{
     return x << 1;
}
int rs(int x)
{
     return x << 1 | 1;
}
void push_up(int x)
{
     sum[x] = sum[ls(x)] + sum[rs(x)];
}
void build(int x, int lft, int rgt)
{
     tag[x] = 0;
     if (lft == rgt)
     {
          sum[x] = a[lft];
          return;
     }
     int mdl = (lft + rgt) >> 1;
     build(ls(x), lft, mdl);
     build(rs(x), mdl + 1, rgt);
     push_up(x);
}
void work(int x, int lft, int rgt, int tg)
{
     tag[x] += tg;
     sum[x] += tg * (rgt - lft + 1);
}
void push_down(int x, int lft, int rgt)
{
     int mdl = (lft + rgt) >> 1;
     work(ls(x), lft, mdl, tag[x]);
     work(rs(x), mdl + 1, rgt, tag[x]);
     tag[x] = 0;
}
void change(int needl, int needr, int lft, int rgt, int x, int tg)
{
     if (needl <= lft && needr >= rgt)
     {
          tag[x] += tg;
          sum[x] += tg * (rgt - lft + 1);
          return;
     }
     push_down(x, lft, rgt);
     int mdl = (lft + rgt) >> 1;
     if (needl <= mdl)
          change(needl, needr, lft, mdl, ls(x), tg);
     if (needr > mdl)
          change(needl, needr, mdl + 1, rgt, rs(x), tg);
     push_up(x);
}
int check(int needl, int needr, int lft, int rgt, int x)
{
     int answer = 0;
     if (needl <= lft && needr >= rgt)
     {
          return sum[x];
     }
     int mdl = (lft + rgt) >> 1;
     push_down(x, lft, rgt);
     if (needl <= mdl)
          answer += check(needl, needr, lft, mdl, ls(x));
     if (needr > mdl)
          answer += check(needl, needr, mdl + 1, rgt, rs(x));
     return answer;
}
signed main()
{
     int n, m;
     cin >> n >> m;
     for (int i = 1; i <= n; i++)
     {
          cin >> a[i];
     }
     build(1, 1, n);
     for (int i = 0; i < m; i++)
     {
          int opt;
          cin >> opt;
          if (opt == 1)
          {
               int a, b, k;
               cin >> a >> b >> k;
               change(a, b, 1, n, 1, k);
          }
          if (opt == 2)
          {
               int a, b;
               cin >> a >> b;
               cout << check(a, b, 1, n, 1) << endl;
          }
     }
     return 0;
}

看过上面思路部分的大体就能懂了（吧？）

珂 朵 莉 树 ($\mathtt{O\ D\ T}$)

FBI WARNING:下方可能出现大量暴力片段，无关人员请迅速撤离

这里的一部分来自笔者之前的题解吖！

珂朵莉树是一种比线段树更好打，比树状数组更易理解，比分块更暴力的和树一点关系没有的数据结构，作为一个名字里带树的数据结构，他是用 $set$ 维护的（笑）。

珂朵莉树支持的操作其实不少：区间修改、查找 $k$ 大值、区间赋值、区间询问$\dots\dots$其复杂度趋向 $m\log{n}$ 。为什么？我们随后会讲。我们现在只需要知道，珂朵莉树可以切许许多多标程是线段树的题目，并且时不时爆踩标程（雾）。

先来讲解珂朵莉树的有关思想：珂朵莉树的一个重要思想就是找集合里需要修改的部分推平（暴力的气息），再添加这个被推平区间的新点进入集合。（即把用不着的清除，留下一个新的代表）。而从整个集合里找到需要修改的部分，并对其单独修改，靠的是分裂 $\operatorname{split}$ ：

（注：这个集合里的元素都代表一个区间，用结构体实现）

非常玄学的算法，我们画个图尝试理解流程。

以下 $\mathtt{poster}$ 是我的结构体名，主要是因为我最初接触 ODT 的时候写的是一道和海报有关的题……

一、从整个区间里分裂出要修改区间

首先我们需要找到目标位置所在 $\mathtt{poster}$

这里我们二分找到下一个 $\mathtt{poster}$ 的起点。那么下一个 $\mathtt{poster}$ 对应的迭代器减去 1 ，就是 $pos$ 所在的这个 $\mathtt{poster}$ 的位置。

将 $pos$ 在的这个 $\mathtt{poster}$ 分割成 $l$~$pos-1$ 和 $pos$~$r$ 两个 $\mathtt{poster}$ 。这样我们就可以单独处理一部分的区间了。具体操作就是直接删掉这整个大块区间，然后再插入两个小块的区间（暴力气息逐渐浓厚）。实现如下～

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#define IT set<node>::iterator//纯粹懒得打
struct node
{
     int l, r;
     mutable int val;
//我们知道set里的普通元素是不能修改的，这里的mutable可以解决这一问题。
     node(int a=0,int b=0,int c=0)
     {
          l = a;
          r = b;
          val = c;
     }
     bool operator <(const node a)const
     {
          return l < a.l;
     }//重载运算符<，便于处理区间时从左到右处理
};
set<node> s;
IT split(int pos)
//将“pos所在 poster ”分裂成“以pos为界线”的两个小 poster
{
     IT it= s.lower_bound(node(pos, 0, 0));
     //取下一个 poster 头的位置，也就是“这次要分裂的poster”的右限
     if(it!=s.end()&&it->l==pos)
     {
     //他不是最后一段poster（指位置最后），且他自己就是下一个poster的开头
          return it;
//pos已经在我们“要更改的poster ，即*it”里了
//到时候处理“*it自己所在的poster”
     }
     it--;//应处理上一个poster，这才是“pos所在的poster”
     int L = it->l, R = it->r, VAL = it->val;
     s.erase(it);//这里到下个poster之前的这些位置就先删了
     s.insert(node(L, pos-1, VAL));
     //将我们删除的这个区间的前半部分（l~pos-1)加入集合
     return s.insert(node(pos, R, VAL)).first;
     //将我们删除的这个区间的后半部分(pos~r)加入集合
     //不会有人不知道insert是有pair返回值的，而且返回值的first是插入的位置的吧！(yygq)
}

二、暴力给一个区间赋上新值

这才是整个赋值实现里最精彩的部分，不如看一下图。

我们要把 $x->y$ 赋值成 $val$ ，倘若我们已经把“ $x$ 到他的区间末尾”，“ $y$ 到他的区间头”这两段区间单独分离出来了，他们加在一起就是我们要赋值的区间。

对于这两小块，我们暴力推平他们，暴力插入一个新区间，暴力赋值为 $val$ （毁灭即重建）

这一思想体现在代码里就像下面这样:

1
2
3
4
5
6
7
8
9
10
void assign(int l,int r,int val)
{
     IT it2 = split(r + 1), it1 = split(l);
     //因为我们处理时是默认是左闭右开的区间，所以要找到r+1
     //先找r+1防的是分离l的时候不小心把r+1所在区间删了
     s.erase(it1, it2);
     //这段都扬喽
     s.insert(node(l, r, val));
     //插回一个新代表，代表的val是我们要赋的新值
}

三、暴力修改我们的区间

这里的大体思想极其简单：把要修改的部分里的最左边，从他原来所属的 $\mathtt{poster}$ 分离出来。最右边也从他原来所属的区间分离出来。再把最左边到最右边中间的每一个 $\mathtt{poster}$ 暴力修改。

（暴力气息扑面而来）

如图：

我们把左边分离出来，右边分离出来，中间的每一段，我们直接修改他的 $val$ 。代码如下：

1
2
3
4
5
6
7
8
9
void update(int l, int r, int k)
{
     IT it2 = split(r + 1), it1 = split(l);
     //把左右界确定好，以相同的原因先it2再it1
     for (IT i = it1; i != it2; i++)
     {
          i->val += k;//暴力修改
     }
}

就短$\dots\dots$

四、暴力查找区间第k大

这里我们的做法是： $\operatorname{sort}$ 。

没错，真就 $\operatorname{sort}$ 。不过既然到了珂朵莉树这里，又要进行一些本地化处理。

我们大体流程是这样的：

  1. 取出这段区间里所有 $\mathtt{poster}$ ，将其化为 <权值，拥有该权值的区间长度> 的 pair ，并存进一个 vector ，也就是对于一个 $\mathtt{poster}$ 化成一个 make_pair(val,r-l+1) 的元素。

  2. 对这个区间暴力 $\operatorname{sort}$ 。

  3. 从 $begin$ 往 $end$ 开搜，每次我们跑过一个元素，就把 $k$ （区间第k大的那个k）减去这个元素的 $second$ ，相当于我们跑过了这些元素，消耗里这么多排名。跑过一个以后，我们看看 $k$ 是不是变得小于 0 。小于0则说明我们跑过头了，那我们刚刚跑过的那个元素，不就是我们要找的嘛， $return$ 了。

实现不难了吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int rankk(int l, int r, int k)
{
     vector<pair<int, int>> v;//开vector!
     IT it2 = split(r + 1), it1 = split(l);//分出左右界
     v.clear();
     for (IT i = it1; i != it2; i++)
     {
          int l = i->l, r = i->r, val = i->val;
          v.push_back(make_pair(val, r - l + 1));
          //权值val，以及“以val为权值的区间”里的单点个数
     }
     sort(v.begin(), v.end());
     //violence!!!
     for (VIT i = v.begin(); i != v.end(); i++)
     {
          k -= i->second;
          //跑过一个元素
          if (k <= 0)//跑过头，也就是找到了
               return i->first;
     }
     return -1;
}

妙过头了。

我们再来考虑之前的复杂度问题，为什么珂朵莉树可以逼近甚至超越线段树？其实很好解释，我们的 $set$ 里的元素可不是始终有 $N$ 个，我们经过 $\operatorname{assign}$ 的清除元素留代表的工作，已经在不断地消减我们的工作量，最终这里的工作量是趋于 $\log{n}$ 的（玄学）。

这里放一下ODT板子题也是其发源地 CF896C （这道题以前是个黑，刚刚变成紫了，呜呜呜～）的完整代码叭。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <bits/stdc++.h>
using namespace std;
#define IT set<node>::iterator
#define VIT vector<pair<int, int>>::iterator
#define int long long
struct node
{
     int l, r;
     mutable int val;
     node(int a, int b, int c)
     {
          l = a, r = b, val = c;
     }
     bool operator<(const node a) const
     {
          return l < a.l;
     }
};
set<node> s;
int MOD;
int n, m, seed, vmax;
IT split(int pos)
{
     IT it = s.lower_bound(node(pos, 0, 0));
     if (it != s.end() && it->l == pos)
     {
          return it;
     }
     it--;
     int l = it->l, r = it->r, val = it->val;
     s.erase(it);
     s.insert(node(l, pos - 1, val));
     return s.insert(node(pos, r, val)).first;
}
void assign(int l, int r, int val)
{
     IT it2 = split(r + 1), it1 = split(l);
     s.erase(it1, it2);
     s.insert(node(l, r, val));
}
void update(int l, int r, int k)
{
     IT it2 = split(r + 1), it1 = split(l);
     for (IT i = it1; i != it2; i++)
     {
          i->val += k;
     }
}
int rankk(int l, int r, int k)
{
     vector<pair<int, int>> v;
     IT it2 = split(r + 1), it1 = split(l);
     v.clear();
     for (IT i = it1; i != it2; i++)
     {
          int l = i->l, r = i->r, val = i->val;
          v.push_back(make_pair(val, r - l + 1));
     }
     sort(v.begin(), v.end());
     for (VIT i = v.begin(); i != v.end(); i++)
     {
          k -= i->second;
          if (k <= 0)
               return i->first;
     }
     return -1;
}
int quick_pow(int a, int exp)
{
     if (exp == 1)
     {
          return a % MOD;
     }
     int tmp = quick_pow(a, exp / 2);
     if (exp % 2 == 0)
     {
          return (tmp * tmp) % MOD;
     }
     else
     {
          return ((tmp * tmp) % MOD * a) % MOD;
     }
}
int powsum(int l, int r, int exp)
{
     IT it2 = split(r + 1), it1 = split(l);
     int res = 0;
     for (IT i = it1; i != it2; i++)
     {
          int l = i->l, r = i->r, val = i->val;
          res = (res + (r - l + 1) * quick_pow(val % MOD, exp) % MOD) % MOD;
     }
     return res;
}
inline int rnd()
{
     int ret = seed;
     seed = (seed * 7 + 13) % 1000000007;
     return ret;
}
signed main()
{
     scanf("%lld%lld%lld%lld", &n, &m, &seed, &vmax);
     for (int i = 1; i <= n; i++)
     {
          int num = rnd() % vmax + 1;
          s.insert(node(i, i, num));
     }

     for (int i = 1; i <= m; i++)
     {
          int op = (rnd() % 4) + 1;
          int l = (rnd() % n) + 1;
          int r = (rnd() % n) + 1;
          if (l > r)
               swap(l, r);
          int x;
          if (op == 3)
          {
               x = (rnd() % (r - l + 1)) + 1;
          }
          else
               x = (rnd() % vmax) + 1;
          if (op == 4)
          {
               MOD = (rnd() % vmax) + 1;
          }
          if (op == 1)
          {
               update(l, r, x);
          }
          if (op == 2)
          {
               assign(l, r, x);
          }
          if (op == 3)
          {
               cout << rankk(l, r, x) << endl;
          }
          if (op == 4)
          {
               cout << powsum(l, r, x) << endl;
          }
     }
     return 0;
}

比平衡树好打多了～

这里友情提醒：珂朵莉树基本上永远不是我们做一道题目的唯一解或者首选项，因为他的复杂度 是 假 的。有可能会被卡（不过出题人如果不刻意卡他应该还好），所以ODT一般是我们的第二屏障，要是正解真的写不出来，还是可以期待暴力碾标算的奇迹的。（逃

终于写完辣！这里列举的只是一些较为基础的数据结构，普及选手顺手拿个1=应该是游刃有余，提高的话，想要往上走走还是要往深里学（或许

第1008行题解撒花～～～

最后更新： 2021年04月17日 16:14

原始链接： https://quest233.github.io/2021/04/17/%E6%B5%85%E8%B0%88%E7%AE%80%E5%8D%95%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/