Hi all!
Recently, I tried to implement a HLD struct. However, my local computer shows Segmentation Fault verdict as soon as I set the constraint of N to 1e5, the online judge shows TLE verdict btw. Small constraint on N works just fine. Here is the code:
Segmentation Fault Code
#include<bits/stdc++.h>
using namespace std;
#define nl '\n'
const int N = 1e5 + 5;
int n;
template<typename seg_t>
struct HLD{
int P[N][20];
int parent[N];
int depth[N];
int child[N];
int bigChild[N];
int chain[N];
seg_t arr[N];
seg_t tree[3 * N];
int label[N];
int label_time = 0;
vector<int> g[N];
void update(int u, int low, int high, int idx, int val){
if(low > idx || high < idx) return;
if(low == high){
tree[u] = val;
return;
}
int mid = (low + high) / 2;
update(2 * u, low, mid, idx, val);
update(2 * u + 1, mid + 1, high, idx, val);
tree[u] = tree[2 * u] ^ tree[2 * u + 1];
}
seg_t get(int u, int low, int high, int l, int r){
if(low > r || high < l) return 0;
if(low >= l && high <= r) return tree[u];
int mid = (low + high) / 2;
return get(2 * u, low, mid, l, r) ^ get(2 * u + 1, mid + 1, high, l, r);
}
void init(int root){
for(int i = 0; i < 3 * N; i++)
tree[i] = 0;
for(int i = 1; i < n; i++){
int u, v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 0; i <= n; i++){
parent[i] = -1;
chain[i] = i;
}
parent[root] = root;
dfs(root, 0);
buildLCA();
dfs_labels(arr, 1, -1);
}
void dfs(int u, int level){
depth[u] = level;
child[u] = 1;
int bigc = -1, bigv = -1;
for(auto x: g[u]){
if(parent[x] == -1){
parent[x] = u;
dfs(x, level + 1);
child[u] += child[x];
if(child[x] > bigv){
bigc = x;
bigv = child[x];
}
}
}
bigChild[u] = bigc;
}
void buildLCA(){
for(int i = 0; i <= n; i++){
for(int j = 1; j <= trunc(log2(n)); j++)
P[i][j] = -1;
}
for(int i = 1; i <= n; i++)
P[i][0] = parent[i];
for(int j = 1; j <= trunc(log2(n)); j++)
for(int i = 0; i <= n; i++)
if(P[i][j - 1] != -1) P[i][j] = P[P[i][j - 1]][j - 1];
}
int lca(int u, int v){
if(depth[u] < depth[v]) swap(u, v);
int x = 1;
while(x <= log2(depth[u])) x++;
x--;
for(int i = x; i >= 0; i--)
if(depth[u] - (1<<i) >= depth[v]) u = P[u][i];
if(u == v) return u;
for(int i = x; i >= 0; i--)
if(P[u][i] != -1 && P[u][i] != P[v][i])
u = P[u][i], v = P[v][i];
return parent[u];
}
int k_th_ancestor(int u, int k){
if(k == 0) return u;
int cur = u;
for(int i = 17; i >= 0; i--){
if(k >= pow(2, i)){
k -= pow(2, i);
cur = P[cur][i];
}
}
return cur;
}
void dfs_labels(seg_t* a, int u, int v){
label[u] = label_time++;
update(1, 0, n - 1, label[u], a[u]);
if(bigChild[u] != -1) dfs_labels(a, bigChild[u], u);
for(auto x: g[u]){
if(x != v && x != bigChild[u])
dfs_labels(a, x, u);
}
}
void dfs_chains(int u, int v){
if(bigChild[u] != -1) chain[bigChild[u]] = chain[u];
for(auto x: g[u]){
if(x == v) continue;
dfs_chains(x, u);
}
}
seg_t query_chain(int u, int p){
seg_t res = 0;
while(depth[p] < depth[u]){
int top = chain[u];
if(depth[top] <= depth[p]){
int diff = depth[u] - depth[p];
top = k_th_ancestor(u, diff - 1);
}
res = res ^ get(1, 0, n - 1, label[top], label[u]);
u = parent[top];
}
return res;
}
seg_t query(int u, int v){
int anc = lca(u, v);
seg_t res = query_chain(u, anc) ^ query_chain(v, anc);
res ^= get(1, 0, n - 1, label[anc], label[anc]);
return res;
}
};
void Solve(){
int q;
cin>>n>>q;
HLD<int> h;
for(int i = 1; i <= n; i++)
cin>>h.arr[i];
h.init(1);
while(q--){
int t, x, y;
cin>>t>>x>>y;
if(t == 1) h.update(1, 0, n - 1, h.label[x], y);
else cout<<h.query(x, y)<<nl;
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
Solve();
}
So, I tried to rewrite the same code without using struct. This time my local computer ran smoothly and the online judge showed AC verdict.
The AC code:
#include<bits/stdc++.h>
using namespace std;
#define nl '\n'
const int N = 1e5 + 5;
int n;
vector<int> g[N];
int arr[N];
int bigChild[N];
int child[N];
int depth[N];
int chain[N];
int label[N], label_time;
int parent[N];
int lca_lift[N][20];
int tree[3 * N];
int k_th_ancestor(int u, int k);
void lca_dfs(int u, int p);
void dfs_size(int u, int p, int level);
void dfs_chains(int u, int p);
void dfs_labels(int u, int p);
void update(int u, int low, int high, int idx, int val){
if(low > idx || high < idx) return;
if(low == high){
tree[u] = val;
return;
}
int mid = (low + high) / 2;
update(2 * u, low, mid, idx, val);
update(2 * u + 1, mid + 1, high, idx, val);
tree[u] = tree[2 * u] ^ tree[2 * u + 1];
}
int get(int u, int low, int high, int l, int r){
if(low > r || high < l) return 0;
if(low >= l && high <= r) return tree[u];
int mid = (low + high) / 2;
return get(2 * u, low, mid, l, r) ^ get(2 * u + 1, mid + 1, high, l, r);
}
void init_arrays(){
for(int i = 0; i < N; i++)
chain[i] = i;
for(int i = 0; i < 3 * N; i++)
tree[i] = 0;
}
void addEdge(int u, int v){
g[u].push_back(v);
g[v].push_back(u);
}
void initTree(int root){
lca_dfs(root, -1);
dfs_size(root, -1, 0);
dfs_chains(root, -1);
label_time = 0;
dfs_labels(root, -1);
}
void lca_dfs(int u, int p){
lca_lift[u][0] = p;
for(int i = 1; i < 20; i++){
if(lca_lift[u][i - 1] == -1) lca_lift[u][i] = -1;
else lca_lift[u][i] = lca_lift[lca_lift[u][i - 1]][i - 1];
}
for(auto x: g[u])
if(x != p) lca_dfs(x, u);
}
void dfs_size(int u, int p, int level){
child[u] = 1;
depth[u] = level;
parent[u] = p;
int bigc = -1, bigv = -1;
for(auto x: g[u]){
if(x == p) continue;
dfs_size(x, u, level + 1);
child[u] += child[x];
if(child[x] > bigv){
bigv = child[x];
bigc = x;
}
}
bigChild[u] = bigc;
}
void dfs_chains(int u, int p){
if(bigChild[u] != -1) chain[bigChild[u]] = chain[u];
for(auto x: g[u]){
if(x == p) continue;
dfs_chains(x, u);
}
}
void dfs_labels(int u, int p){
label[u] = label_time++;
update(1, 0, n - 1, label[u], arr[u]);
if(bigChild[u] != -1) dfs_labels(bigChild[u], u);
for(auto x: g[u]){
if(x == p || x == bigChild[u]) continue;
dfs_labels(x, u);
}
}
int lca(int a, int b){
if(depth[a] < depth[b]) swap(a, b);
int d = depth[a] - depth[b];
int u = k_th_ancestor(a, d);
if(u == b) return u;
for(int i = 19; i >= 0; i--){
if(lca_lift[u][i] != lca_lift[b][i]){
u = lca_lift[u][i];
b = lca_lift[b][i];
}
}
return lca_lift[b][0];
}
int k_th_ancestor(int u, int k){
for(int i = 19; i >= 0; i--){
if(u == -1) return u;
if((1 << i) <= k){
u = lca_lift[u][i];
k -= (1 << i);
}
}
return u;
}
int query_chain(int u, int v){
int res = 0;
while(depth[v] < depth[u]){
int top = chain[u];
if(depth[top] <= depth[v]){
int diff = depth[u] - depth[v];
top = k_th_ancestor(u, diff - 1);
}
res ^= get(1, 0, n - 1, label[top], label[u]);
u = parent[top];
}
return res;
}
int query(int u, int v){
int anc = lca(u, v);
int res = query_chain(u, anc) ^ query_chain(v, anc);
return res ^ get(1, 0, n - 1, label[anc], label[anc]);
}
void Solve(){
int q;
cin>>n>>q;
for(int i = 0; i < n; i++)
cin>>arr[i];
init_arrays();
for(int i = 1; i < n; i++){
int u, v;
cin>>u>>v;
u--; v--;
addEdge(u, v);
}
initTree(0);
while(q--){
int t, x, y;
cin>>t>>x>>y;
if(t == 1) update(1, 0, n - 1, label[x - 1], y);
else cout<<query(x - 1, y - 1)<<nl;
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
Solve();
}
Could someone plz explain why's there a difference verdict in my codes? Where did I get it wrong? I much appreciate it!
Probably, stack overflow (you allocated a variable of your struct on the stack, and the size of the variable is about 12Mb).
both codes have the same constraint of N. So if the struct version got stack overflow, should the other version got the same verdict? I don't really get it.
In the first version you use the stack for the local variable h, in the second version the memory is allocated statically.
so that's how struct works? Tks!
You can use vectors instead of arrays in the struct and your first version will work without such issues.
I just figured out the problem. The first version of code works OK when I declare the struct globally. Damn, I'm clueless
Similarly, the AC code got Segmentation Fault if I declare the struct locally
It does not matter whether you use struct or just define local variable buffer as
char buffer[sizeof(HLD)];. If the stack size is less than sizeof(HLD), you get stack overflow in any case.That's why it's so weird that the code gets segmentation fault if I declare struct locally (N = 1e5) and run smoothly when I declare struct globally. I just don't get it
What do you expect if you have only 8Mb for local variables but one of your local variables is of bigger size? When you declare variables in the global scope, the stack is not used for them.
)
upload photos to the internet
)
You can try replacing
HLD<int> h;byauto& h = *(new HLD<int>{});— this will prevent it from being allocated on the stack.If you care about memory leaks, here's an ugly hack:
Thank a lot!
I believe this is because of stack vs heap allocation, the stack is a rather small section of the memory that (for development purposes) is mostly just meant to hold pointers to real data. (Eg. Your stack might be 8-16Mb and your heap might be the rest of your memory)
When you create(instantiate) a struct inside a function, the memory is allocated on the stack. In the case above, the struct holds a lot of arrays (arrays declared like this are also allocated in the same place as your struct) and so you overflow the amount of memory your stack actually has. (stack overflow)
In the global case however, all your variables are, well, global. And by default all global variables are allocated on the heap, so you don't get any problems
This is why when you create your struct globally it works, because the struct and all the arrays you create move to the heap.
If you ever encounter something like this these are things you can try
1. use vector instead of int arr[n]: internally vector actually uses pointers to store the data, and all the data is allocated on the heap
2. Use pointers instead of int arr[n]: Same logic as vector but DIY. This comes with the extra headache of having to free the memory yourself so I wouldn't do it.
3. Declare your struct globally: as you did
4. Use pointer to struct: same logic as pointer to arrays for the data, but you make (and are responsible for freeing) just the one pointer
That's really comprehensive. Thank you!