Tree Flattening (Euler Tour) + BIT/SegTree

Competitive programming often reduces complex structures to simpler forms. With trees, the most useful reduction is an Euler tour that flattens each subtree into a contiguous range of indices. Once you have that, you can answer many subtree queries using a Fenwick Tree (BIT) or a Segment Tree as if you were working on a plain array.

Quick Overview — Do a DFS and assign each node an entry time tin[u]. Every subtree becomes a range [tin[u], tout[u]]. Then:

Point update / Subtree sum → use BIT.

Subtree add / Point query → BIT with range-add trick.

Subtree add / Subtree sum → Lazy Segment Tree or the two-BIT trick.

Edge queries → store edge weight on the child, then treat like node values.

Why Flatten a Tree?

Subtree queries are awkward because children are scattered in adjacency lists. An Euler tour (entry-time ordering) maps the entire subtree of u to a single contiguous segment in a flattened array:

Visit u → set tin[u] = ++timer.
After exploring u's whole subtree → tout[u] = timer.
Subtree of u ↔ indices tin[u]..tout[u].

This turns subtree problems into range problems, exactly what BITs and Segment Trees are good at.

Euler Tour Essentials (Entry/Exit Times)

We use the “Euler Tour I” variant where each node appears once.

tin[u]: time when DFS first visits u.
tout[u]: last index covered by u’s subtree.
Subtree of u ↔ [tin[u], tout[u]].

Example DFS order for the tree below could be 1, 2, 3, 5, 4:

Then tin[3]=3, tout[3]=4, so subtree(3) is [3..4].

BIT vs Segment Tree

Fenwick (BIT): Simple and fast for sums. Supports:
- Point add + Range sum, or
- Range add + Point query (with the difference-array trick).
- With a small extension (two BITs), you can do Range add + Range sum.
Segment Tree (Lazy): General-purpose; cleanly supports Range add + Range sum, Range assign, Range max/min, etc.

Point to keep in mind:

Only point updates + subtree sums → BIT.
Subtree updates + subtree sums (or max/min) → Lazy Segment Tree.

Patterns

1) Point update on a node, query sum over a subtree

Build flat[] with flat[tin[u]] = val[u].
Subtree sum of u → sum over flat[tin[u]..tout[u]].

Data structure: 1 BIT (point add, prefix sum)

Ops:

Update node u by +delta → add(tin[u], delta).
Query subtree u → sum(tout[u]) - sum(tin[u]-1).

2) Add to all nodes in a subtree, query a single node

Subtree add is range add on [tin[u], tout[u]]. Node query is point query at tin[u].

Data structure: 1 BIT using the range-add trick

Range add [L..R] of +x:

add(L, +x), add(R+1, -x).
Value at index i = prefix sum at i.

So to add x to subtree(u): add(tin[u], +x), add(tout[u]+1, -x).
To get value at node u: prefix sum at tin[u].

3) Add to a subtree, query sum of a subtree

This is range add + range sum. Choose one:

Lazy Segment Tree, or
Two-BIT trick.

Two-BIT recap (array 1..N): maintain BITs B1, B2.

Add x on [L..R]: add(B1, L, +x); add(B1, R+1, -x); add(B2, L, +x*(L-1)); add(B2, R+1, -x*R);

Prefix sum at p = p * sum(B1,p) - sum(B2,p) Range sum [L..R] = pref(R) - pref(L-1)

Map [L..R] to [tin[u]..tout[u]].

4) Edge updates / queries

Root the tree. For each non-root v, map the weight of edge (parent[v], v) to position tin[v]. Then treat edge queries exactly like node-value queries on the flattened array.

Note: For path queries (u–v), Euler flattening alone does not make the path contiguous. Use HLD (Heavy-Light Decomposition) or offline methods (e.g., Mo’s on trees). This post focuses on subtree-friendly queries.

Implementation: Contest-Ready Templates

A) Euler Tour + BIT (point update, subtree sum)

Supports commands:

a u x → add x to node u.
s u → sum of values in subtree of u.

#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    int n; vector<long long> bit;
    Fenwick(int n=0): n(n), bit(n+1,0) {}
    void add(int i, long long v){ for(; i<=n; i+=i&-i) bit[i]+=v; }
    long long sum(int i){ long long s=0; for(; i>0; i-=i&-i) s+=bit[i]; return s; }
    long long sum(int l,int r){ if(l>r) return 0; return sum(r)-sum(l-1); }
};

int n,q;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>q;
    vector<long long> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    vector<vector<int>> g(n+1);
    for(int i=0;i<n-1;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); }
    vector<int> tin(n+1), tout(n+1);
    int timer=0;
    function<void(int,int)> dfs = [&](int u,int p){
        tin[u]=++timer;
        for(int v: g[u]) if(v!=p) dfs(v,u);
        tout[u]=timer;
    };
    dfs(1,0);
    Fenwick fw(n);
    for(int u=1;u<=n;u++) fw.add(tin[u], a[u]);
    while(q--){
        char t; cin>>t;
        if(t=='a'){ int u; long long x; cin>>u>>x; fw.add(tin[u], x); }
        else { int u; cin>>u; cout<<fw.sum(tin[u], tout[u])<<"\n"; }
    }
}

Complexity: O((n+q) log n).

B) Euler Tour + Lazy Segment Tree (subtree add, subtree sum)

Supports commands:

a u x → add x to every node in subtree of u.
s u → sum of values in subtree of u.

#include <bits/stdc++.h>
using namespace std;

struct SegTree{
    int n; vector<long long> t,lz;
    SegTree(int n=0): n(n), t(4*n+4,0), lz(4*n+4,0) {}
    void build(int v,int tl,int tr, const vector<long long>& a){
        if(tl==tr){ t[v]=a[tl]; return; }
        int tm=(tl+tr)>>1;
        build(v<<1,tl,tm,a);
        build(v<<1|1,tm+1,tr,a);
        t[v]=t[v<<1]+t[v<<1|1];
    }
    void push(int v,int tl,int tr){
        if(!lz[v]) return;
        int tm=(tl+tr)>>1;
        apply(v<<1,tl,tm,lz[v]);
        apply(v<<1|1,tm+1,tr,lz[v]);
        lz[v]=0;
    }
    void apply(int v,int tl,int tr,long long x){
        t[v]+=x*(tr-tl+1);
        lz[v]+=x;
    }
    void add(int v,int tl,int tr,int l,int r,long long x){
        if(l>r) return;
        if(l<=tl && tr<=r){ apply(v,tl,tr,x); return; }
        push(v,tl,tr);
        int tm=(tl+tr)>>1;
        if(l<=tm) add(v<<1,tl,tm,l,min(r,tm),x);
        if(r>tm) add(v<<1|1,tm+1,tr,max(l,tm+1),r,x);
        t[v]=t[v<<1]+t[v<<1|1];
    }
    long long sum(int v,int tl,int tr,int l,int r){
        if(l>r) return 0;
        if(l<=tl && tr<=r) return t[v];
        push(v,tl,tr);
        int tm=(tl+tr)>>1;
        long long res=0;
        if(l<=tm) res+=sum(v<<1,tl,tm,l,min(r,tm));
        if(r>tm) res+=sum(v<<1|1,tm+1,tr,max(l,tm+1),r);
        return res;
    }
};

int n,q;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>q;
    vector<long long> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    vector<vector<int>> g(n+1);
    for(int i=0;i<n-1;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); }
    vector<int> tin(n+1), tout(n+1);
    int timer=0;
    function<void(int,int)> dfs = [&](int u,int p){
        tin[u]=++timer;
        for(int v: g[u]) if(v!=p) dfs(v,u);
        tout[u]=timer;
    };
    dfs(1,0);
    vector<long long> flat(n+1);
    for(int u=1;u<=n;u++) flat[tin[u]]=a[u];
    SegTree st(n);
    st.build(1,1,n,flat);
    while(q--){
        char t; cin>>t;
        if(t=='a'){ int u; long long x; cin>>u>>x; st.add(1,1,n,tin[u],tout[u],x); }
        else { int u; cin>>u; cout<<st.sum(1,1,n,tin[u],tout[u])<<"\n"; }
    }
}

Complexity: O((n+q) log n).

Resources:

Happy coding and keep solving!