关于一些卡空间小寄巧

· · 个人记录

众所周知，OI 是一个吝啬空间压榨时间的神奇竞赛，很多时候我们需要将空间尽可能控制在一个合理的范围内。于是各种优化空间的神仙操作就出现了。

所以我来稍微总结一下，有遗漏或者错误的内容换欢迎反馈。

真的会谢 qwq

qwq \

bitset

bitset 可以用来代替 bool，而且这玩意儿空间奇小，常数更是 \frac{1}{32}，非常秀。相关的用法可以看 洛谷日报，上面写得还是很清楚的。

\

short

作为一个耳熟能详的数字：32767，代表的正是 short 的最大取值。

有些时候，数字的值域会比较小，这个时候就可以用 short 去优化空间。可以直接将空间优化到原来的一半，效果还是十分显著的。

美中不足就是适用范围比较小，因为许多题的数据范围都是在 10^5 等，这时候 short 就不能用了，比较可惜。

关于 short 的读入，输出，如果你使用 cin cout 就没问题，如果用 scanf printf 的话需要注意写法：

short x;
scanf("%hd", &x);
printf("%hd\n", x);

并不是很难记，而且就算没记住，考场上编译器也能检查出来的。

\

char

同 short，如果值域甚至小于 128，你甚至可以用 char 去存储。没关系，除了阴间亿点也没什么（）

本人有幸写过（）

\

位域 (bit-field)

我第一次接触这个东西是在这道题：

CF543E Listening to Music

这里面开主席树的时候结构体要占很大空间。我最初的写法是这样的：

struct node { int ls, rs, mx; } t[maxn*40];

结果当然是理所当然地 Memory Limited Exceeded on #1（悲

然后我翻开题解一看，嚯，大佬的写法秀了我一脸：

struct Node {
    ull mx : 18, ls : 23, rs : 23; 
} t[MAX_N * 40];

我：？？？怎么开 unsigned long long 比我 int 空间还小？？

后来上网 bdfs 后了解到，这是一种名为位域的写法。

比如要写一个结构体，里面有三个元素，你写了三个 int：

struct node {          
    int x, y, z;       
} ;                    

int main() {           
    node px;           
    printf("size of px is: %lu\n", sizeof(px));             return 0;          
}

然后输出：

size of px is: 12

由于一个 int 占 4 个字节，三个 int 自然占 12 个字节。但是如果告诉你，这三个元素的都是 < 2^{18} 的正整数呢？

可以这么写：

struct node {          
    unsigned long long x : 18, y : 18, z : 18;     
} ;                    

int main() {           
    node px;           
    printf("size of px is: %lu\n", sizeof(px));             return 0;          
}

然后运行，输出：

size of px is: 8

非常神奇。正常一个 unsigned long long 占 8 个字节，也就是 16 位，值域可以表示到 2^{64} - 1。但是这样的写法可以理解为是，将每个元素都分配大小为 2^{18} 的空间，那么相当于一共占了 3 \times 18 = 54 < 64 个 bit，这样就没有超过 64 bit，所以可以同时存在一个 unsigned long long 里。

至于为什么不用 long long？因为 long long 有符号位，这样做避免了空间浪费。当然，如果实在需要用也没问题。

注意 bit 的分配。

\

动态开点线段树 —— 标号存值

相信很多人可持久化线段树的修改与查询操作都是这么写的：

void modify(int& o, int l, int r, int pos, int val) {
    if(!o) o = ++cnt;
    t[o].val += val;
    if(l == r) return;
    if(pos <= mid) modify(t[o].ls, l, mid, pos, val);
    else modify(t[o].rs, mid+1, r, pos, val);
}

int query(int o, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) return t[o].val;
    int res = 0;
    if(ql <= mid) res += query(t[o].ls, l, mid, ql, qr);
    if(mid < qr) res += query(t[o].rs, mid+1, r, ql, qr);
    return res;
}

但是实际上，线段树的最后一层由于不需要再向下递归，也就是说没有儿子。这时候为叶子单独分一整个点出来实在不划算，我们考虑在这个位置只存值，不存儿子。

具体操作就是用点的标号来存储值：

void modify(int& o, int l, int r, int pos, int val) {
    if(l == r) { o += val; return; }
    if(!o) o = ++cnt;
    t[o].val += val;
    if(pos <= mid) modify(t[o].ls, l, mid, pos, val);
    else modify(t[o].rs, mid+1, r, pos, val);
}

然后查询就加上特判即可：

int query(int o, int l, int r, int ql, int qr) {
    if(l == r) return o;
    if(ql <= l && r <= qr) return t[o].val;
    int res = 0;
    if(ql <= mid) res += query(t[o].ls, l, mid, ql, qr);
    if(mid < qr) res += query(t[o].rs, mid+1, r, ql, qr);
    return res;
}
\

循环代替递归

递归不光会带来较大的常数，由于需要存储栈帧，其也会为内存带来比较大的消耗。在内存不够时可以尽可能用循环来代替递归。

或者去把栈开大一点（）

据说有一个大佬考场常数爆炸了，原因是使用了递归写法的快速幂。

我：啊？

\

数组重复利用

可能有些题需要开很多数组，然而某个数组可能在一次使用后就再也用不到了。这时可以用这个数组去存其他数组的值，正好废物利用。

有时候废物利用需要先清理垃圾。因此尽量选择不需要清理垃圾的数组，实在没有了再去清垃圾。尽量控制常数。

毕竟时间换空间什么的实在是很亏（）

qwq