首页 > 代码库 > 平衡树(splay)
平衡树(splay)
求区间最大值模板
1 struct node{ 2 int f[maxn];//父亲结点 3 int ch[maxn][2];//左右孩子 4 int key[maxn];//结点i代表的数字 5 int cnt[maxn];//结点i出现的次数,也可以为全值。平衡树没有相同值的结点,所以如果出现了相同值时,cnt[i]++,或者cnt[i] += key[i] 6 int siz[maxn];//包括i的子树的大小 7 int val[maxn]; 8 int Max[maxn]; 9 int add[maxn]; 10 bool rev[maxn]; 11 12 int sz;//整棵子树的大小 13 int root;//树根 14 node(){ 15 sz = root = 0; 16 } 17 inline void Clear(int x){//清零,一般用于删除之后 18 ch[x][0] = ch[x][1] = f[x] = cnt[x] = key[x] = siz[x] = 0; 19 } 20 21 inline int Get(int x){//用于判断左孩子还是右孩子 22 return ch[f[x]][1] == x; 23 } 24 25 inline void Up(int x){//更新当前点的值,一般用于修改之后 26 if(x){ 27 siz[x] = cnt[x]; 28 if(ch[x][0]) siz[x] += siz[ch[x][0]]; 29 if(ch[x][1]) siz[x] += siz[ch[x][1]]; 30 } 31 } 32 ///boss 来了 33 inline void Rotate(int x){ 34 int fa = f[x]; 35 int fafa = f[fa]; 36 int k = Get(x);//判断是左孩子还是右孩子 37 ch[fa][k] = ch[x][k^1]; f[ch[fa][k]] = fa; 38 f[fa] = x; ch[x][k^1] = fa; 39 f[x] = fafa; 40 if(fafa){ 41 ch[fafa][ch[fafa][1]==fa]=x; 42 } 43 pushUp(fa); 44 Up(fa); 45 Up(x); 46 } 47 48 inline void Splay(int x,int goal){//将x旋转到goal,goal为0表示旋转到根 49 if(x == goal) return; 50 while(f[x] != goal){ 51 int y = f[x],z =f[y]; 52 pushDown(z),pushDown(y),pushDown(x); 53 Rotate(x); 54 } 55 pushUp(x); 56 if(goal == 0) root = x; 57 } 58 59 inline void Insert(int v){//插入一个值为V的点 60 if(root == 0){sz++;ch[sz][0]=ch[sz][1]=f[sz]=0;key[sz]=v;cnt[sz]=1;siz[sz]=1;root=sz;return;} 61 int now = root,fa = 0; 62 while(1){ 63 if (key[now] == v){ 64 cnt[now]++; 65 Up(now); 66 Up(fa); 67 Splay(now,0); 68 break; 69 } 70 fa = now; 71 now = ch[now][key[now]<v]; 72 if(now == 0){ 73 sz++; 74 ch[sz][0] = ch[sz][1] = 0; 75 key[sz] = v; siz[sz] = 1; 76 cnt[sz] = 1; f[sz] = fa; 77 ch[fa][key[fa]<v] = sz; 78 Up(fa); 79 Splay(sz,0); 80 break; 81 } 82 } 83 } 84 85 inline int Find(int v){//查找值为v的点的排名,就是第几大 86 int ans = 0,now = root; 87 while(1){ 88 if(v < key[now]){ 89 now = ch[now][0]; 90 } 91 else{ 92 ans += (ch[now][0] ? siz[ch[now][0]] : 0); 93 if(v == key[now]){ 94 Splay(now,0); 95 return ans + 1; 96 } 97 ans += cnt[now]; 98 now = ch[now][1]; 99 } 100 } 101 } 102 103 inline int Findx(int x){//z找到排名为x的点的值 104 int now = root; 105 while(1){ 106 if(ch[now][0] && x <= siz[ch[now][0]]) 107 now = ch[now][0]; 108 else{ 109 int temp = (ch[now][0] ? siz[ch[now][0]] : 0) + cnt[now]; 110 if( x <= temp ) 111 return key[now]; 112 x -= temp; 113 now = ch[now][1]; 114 } 115 } 116 } 117 ///划重点! 求x的前驱(后继),前驱(后继)定义为小于(大于)x,且最大(最小)的数 118 ///先对x进行Insert操作,然后对于前驱后继对应pre与next,获得结果后记得把x ,Del掉!!!很关键 119 inline int Pre(){//前驱 120 int now = ch[root][0]; 121 while(ch[now][1]) now = ch[now][1]; 122 return now; 123 } 124 125 inline int Next(){//后继 126 int now = ch[root][1]; 127 while(ch[now][0]) now = ch[now][0]; 128 return now; 129 } 130 131 inline void Del(int x){//删除值为x的点 132 int whatever = Find(x); 133 if(cnt[root] > 1){cnt[root]--;return;} 134 if(!ch[root][0] && !ch[root][1]) {Clear(root),root=0;return;} 135 if(!ch[root][0]){ 136 int oldroot = root; 137 root = ch[root][1]; 138 f[root]=0; 139 Clear(oldroot); 140 return; 141 } 142 else if(!ch[root][1]){ 143 int oldroot = root; 144 root = ch[root][0]; 145 f[root]=0; 146 Clear(oldroot); 147 return; 148 } 149 int leftbig = Pre(),oldroot = root; 150 Splay(leftbig,0); 151 f[ch[oldroot][1]] = root; 152 ch[root][1] = ch[oldroot][1]; 153 Clear(oldroot); 154 Up(root); 155 return; 156 } 157 158 void pushUp(int x){ 159 Max[x] = val[x]; 160 siz[x] = cnt[x]; 161 if(ch[x][0]){ 162 Max[x] = max(Max[x],Max[ch[x][0]]); 163 siz[x] += siz[ch[x][0]]; 164 } 165 if(ch[x][1]){ 166 Max[x] = max(Max[x],Max[ch[x][1]]); 167 siz[x] += siz[ch[x][1]]; 168 } 169 } 170 171 void pushDown(int x){ 172 if(x == 0) return; 173 if(add[x]){ 174 if(ch[x][0]){ 175 val[ch[x][0]] += add[x]; 176 Max[ch[x][0]] += add[x]; 177 add[ch[x][0]] += add[x]; 178 } 179 if(ch[x][1]){ 180 val[ch[x][1]] += add[x]; 181 Max[ch[x][1]] += add[x]; 182 add[ch[x][1]] += add[x]; 183 } 184 add[x] = 0; 185 } 186 if(rev[x]){ 187 if(ch[x][0]) rev[ch[x][0]] ^= 1; 188 if(ch[x][1]) rev[ch[x][1]] ^= 1; 189 swap(ch[x][0],ch[x][1]); 190 rev[x] = 0; 191 } 192 } 193 194 int Select(int pos){//查找pos的位置 195 int u = root; 196 pushDown(u); 197 while(siz[ch[u][0]] != pos){ 198 if(pos < siz[ch[u][0]]) u = ch[u][0]; 199 else{ 200 pos -= siz[ch[u][0]] + 1; 201 u = ch[u][1]; 202 } 203 pushDown(u); 204 } 205 return u; 206 } 207 208 void Update(int L,int R,int Val){//l,r的值 + val 209 int u = Select(L-1), v =Select(R+1); 210 Splay(u,0); 211 Splay(v,u); 212 Max[ch[v][0]] += Val; 213 val[ch[v][0]] += Val; 214 add[ch[v][0]] += Val; 215 } 216 217 void Reverse(int L,int R){//翻转 218 int u = Select(L-1), v =Select(R+1); 219 Splay(u,0); 220 Splay(v,u); 221 rev[ch[v][0]] ^= 1; 222 } 223 224 int Query(int L,int R){//查询l,r的最大值 225 int u = Select(L-1), v =Select(R+1); 226 Splay(u,0); 227 Splay(v,u); 228 return Max[ch[v][0]]; 229 } 230 231 int Build(int L,int R){//建一棵空树 232 if(L > R) return 0; 233 if(L == R){ 234 return L; 235 } 236 int mid = (L+R)>>1,sL,sR; 237 ch[mid][0] = sL = Build(L,mid-1); 238 ch[mid][1] = sR = Build(mid+1,R); 239 f[sL] = f[sR] = mid; 240 pushUp(mid); 241 return mid; 242 } 243 244 void ini(int i,int Val){ 245 val[i] = Max[i] = Val; 246 siz[i] = 1; 247 add[i] = rev[i] = ch[i][0] = ch[i][1] = 0; 248 cnt[i] = 1; 249 } 250 251 void Init(int n){//初始化 相当于建树 252 ini(0,-INF),ini(1,-INF),ini(n+2,-INF); 253 for(int i=2;i<=n+1;i++) ini(i,0); 254 root = Build(1,n+2),f[root] = 0; 255 f[0] = 0; ch[0][1] = root; siz[0] = 0; 256 } 257 }splay;
平衡树(splay)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。