https://www.guwolf.com/category/ICPC%E7%AE%97%E6%B3%95%E5%A6%99%E5%A6%99%E5%B1%8B/ https://www.guwolf.com/archives/big-fenwick.html 2025-03-18T21:14:00+08:00 传统方法的局限在算法竞赛中，树状数组（Fenwick Tree）因其简洁高效的特性被广泛使用。但传统实现需要预先确定数据范围并预分配空间，当值域达到1e18量级时，离散化预处理会带来诸多不便：需要离线处理、增加编码复杂度。动态空间的黑魔法我们可以利用unordered_map的无序容器特性配合树状数组的跳跃特性，实现动态内存分配的树状数组，创建出一个1e18甚至更大的树状数组，可以省去离散化的步骤，同时无需离线#define LL long long unordered_map<LL, LL> tree; const LL N = 1e18 + 10; LL lowbit(LL x) {return x & -x;} void add(LL x, LL v) { while(x <= N) { tree[x] += v; x += lowbit(x); } } LL sum(LL x) { LL sum = 0; while(x) { sum += tree[x]; x -= lowbit(x); } return sum; }实现原理分析空间动态分配：unordered_map仅在访问时创建键值对，实际空间复杂度约为O(q logU)，其中q是操作次数，U是值域大小时间效率折衷：哈希表访问时间复杂度为均摊O(1)，但实际常数比普通数组大，在ICPC比赛中请分析好时间再谨慎使用。优势与代价✅ 优势：对于超大值域无需预处理，支持在线操作节省内存空间（稀疏数据场景）⚠️ 注意事项：时间复杂度常数较大哈希冲突导致时间复杂度最坏至O(n)（可参考自定义哈希篇）实战下面是使用超大树状数组做的题1D Country - AtCoder abc371\_d - Virtual Judge使用建议推荐在以下场景使用该技巧：值域极大但操作次数有限（q ≤ 1e5）需要快速实现原型的情况内存资源紧张的环境