[Tutorial] Path sum queries on a tree using a Fenwick tree
Разница между en2 и en3, 2,161 символ(ов) изменены
## Introduction↵

I've come across several problems that require you to be able to efficiently find the sum of some values on a path from $A$ to $B$ in a tree. One can solve these problems using tree decomposition techniques like heavy-light decomposition or centroid decomposition, but that's a bit of an overkill
 and not very elegant in my opinion.↵

In this blog post, I will describe a way to solve these types of problems using 
just a DFS, a Fenwick tree, and LCA. (as well as a way to solve JOIOC 2013 Synchronization this way).↵

**Note: Whenever I talk about edge $(u, v)$ in this post, I assume that $u$ is the parent of $v$.**


## Prerequisites↵

- DFS↵
- Preorder traversal (DFS order)↵
- Fenwick tree↵
- Binary lifting and LCA↵

## The idea↵

Say you have the following problem:↵

> Given a tree with $N$ nodes, each node $i$ has a value $a_i$ that is initially 0. Support the following 2 types of operations in $O(\log N)$ time:↵
> ↵
> 1. Increase the value of $a_i$ by $X$↵
> 2. Find the sum of $a_i$ on the path from $u$ to $v$ for 2 nodes $u$ and $v$↵

First, we flatten the tree using a preorder traversal. Let the time we enter node $i$ be $tin_i$ and the time we exit it be $tout_i$. Additionally, 
construct a let $b$ be an array/Fenwick tree called $BITof size $2N$.↵

If you're familiar with LCA, you'll know that node $u$ is an ancestor of node $v$ if and only if $tin_u \leq tin_v$ and $tout_u \geq tout_v$.↵

If you're familiar with range updates and point queries with Fenwick trees, you'll know that if we want to incre
mentase the range $[A, B]$ by $X$ in an array/Fenwick tree $BIT$, then we increase $BIT_A[A]$ by $X$ and decrease $BIT_{[B + 1}]$ by $X$. Then when we want to find the value of the element at $C$, we simply query the sum of $BIT_[i]$ for each $i$ from 0 to $C$. This works because if $C$ isn't inside the range of an update, the 2 values we update "cancel out" in the query.↵

We can combine the 2 ideas above to work on trees — if we want to incre
mentase the value of node $u$ by $X$, we increase $BIT_{b[tin_u}]$ by $X$ and decrease $BIT_{b[tout_u + 1}]$ by $X$. Then when we want to find the sum of nodes on the path between node $v$ and the root, we simply query the sum of $BIT_i$ from 0 to $tin_b[i]$ for each $i$ from 0 to $tin_v$. This works because node $w$ only contributes to the sum if $w$ is an ancestor of $v$.↵

We can then use LCA and the principle of inclusion-exclusion to find the sum of nodes/edges on the path between nodes $u$ and $v$.↵

This idea also works if we want to sum edges instead of nodes — when we update edge $(u, v)$, update $b[tin_v]$ and $b[tout_v + 1]$ and make queries similarly.↵

## Problem 1 — [Infoarena Disconnect](https://www.infoarena.ro/problema/disconnect)↵

Here's the gist of the problem:↵

You're given a tree with $N$ nodes. Process $M$ of the following queries online:↵

1. Delete the edge $(u, v)$ from the path.↵
2. Determine whether there is a path from $u$ to $v$.↵

$N \leq 10^5$ and $M \leq 5 \cdot 10^5$↵

### Solution↵

Let the value of each edge in the tree initially be 0. When we "delete" an edge, we just update its value to be 1.↵

Notice how there is a path from $u$ to $v$ if and only if the sum of edges on the path between $u$ and $v$ is 0.↵

We can then apply 
our trickthe above idea and solve this problem in $O(M \log N)$ time.↵

Alternatively,↵

- Find the lowest ancestor $l_u$ of $u$ such that the sum of the edges between $u$ and $l_u$ is 0↵
  - We can do this using binary lifting and our trick↵
- Find $l_v$ similarly for $v$.↵
- Check whether $l_u$ is an ancestor of $v$ and whether $l_v$ is an ancestor of $u$.↵

This solution runs in $O(M \log^2 N)$ time.↵

<spoiler summary="My code for this problem">↵
```cpp↵
#include <bits/stdc++.h>↵
#define FOR(i, x, y) for (int i = x; i < y; i++)↵
typedef long long ll;↵
using namespace std;↵

int n, m;↵

vector<int> graph[100001];↵
int timer = 1, tin[100001], tout[100001];↵
int anc[100001][18];↵

void dfs(int node = 1, int parent = 0) {↵
    anc[node][0] = parent;↵
    for (int i = 1; i < 18 && anc[node][i - 1]; i++)↵
        anc[node][i] = anc[anc[node][i - 1]][i - 1];↵

    tin[node] = timer++;↵
    for (int i : graph[node]) if (i != parent) dfs(i, node);↵
    tout[node] = timer;↵
}↵

int bit[100001];↵

void update(int pos, int val) { for (; pos <= n; pos += (pos & (-pos))) bit[pos] += val; }↵

int query(int pos) {↵
    int ans = 0;↵
    for (; pos; pos -= (pos & (-pos))) ans += bit[pos];↵
    return ans;↵
}↵

int find_ancestor(int node) {↵
    int lca = node;↵
    for (int i = 17; ~i; i--) {↵
        if (anc[lca][i] && query(tin[anc[lca][i]]) == query(tin[node])) lca = anc[lca][i];↵
    }↵
    return lca;↵
}↵

int main() {↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0);↵
    freopen("disconnect.in", "r", stdin);↵
    freopen("disconnect.out", "w", stdout);↵
    cin >> n >> m;↵
    FOR(i, 1, n) {↵
        int a, b;↵
        cin >> a >> b;↵
        graph[a].push_back(b);↵
        graph[b].push_back(a);↵
    }↵
    dfs();↵

    int v = 0;↵
    while (m--) {↵
        int t, x, y;↵
        cin >> t >> x >> y;↵
        int a = x ^ v, b = y ^ v;↵

        if (t == 1) {↵
            if (anc[b][0] == a) swap(a, b);↵
            update(tin[a], 1);↵
            update(tout[a], -1);↵
        } else {↵
            if (find_ancestor(a) == find_ancestor(b)) {↵
                cout << "YES\n";↵
                v = a;↵
            } else {↵
                cout << "NO\n";↵
                v = b;↵
            }↵
        }↵
    }↵
    return 0;↵
}↵

```↵
</spoiler>↵

## Problem 2 &mdash; [JOIOC 2013 Synchronization](https://oj.uz/problem/view/JOI13_synchronization)↵

Here's the gist of the problem:↵

You're given a tree with $N$ nodes. Each edge is initially deactivated and each node stores a unique piece of information.↵

There are $M$ events. During event $i$, the state of exactly 1 edge is toggled.↵

When the edge $(u, v)$ becomes activated, $u$'s component and $v$'s component merge and "sync up". All nodes in the merged component will contain all the information stored on the other nodes in the component.↵

After all these events, you want to know how many unique pieces of information are stored in each node.↵

$N \leq 10^5$ and $M \leq 2 \cdot 10^5$↵

### Solution↵

Firstly, root the tree arbitrarily. Let $a_i$ be the amount of unique information stored on node $i$. Let $c_i$ be the amount of unique information stored on node $i$ 
the last time the edge from node $i$ to its parent was activatedright before the edge from node $i$ to its parent was deactivated.↵

Notice how if we make the edge $(u, v)$ activated, then the new amount of information on all nodes in the merged component is $a_u + a_v - c_v$.↵

This gives us a way to find the amount of information on the merged component, but we still need a way to set each node in the component to have that amount of information.↵

Fortunately, we don't have to do that!↵

Since each node in a component has the same amount of information, we can just store that amount in the "root" (i.e. the lowest node) of the component. Let the root of $i$'s component be $root[i]$. The amount of information stored on $i$ is thus $a_{root[i]}$.↵

When we deactivate the edge $(u, v)$, $v$ becomes the root of its new component and $root[u]$ doesn't change. This means we can simply set $a_v$ and $c_v$ to equal $a_{root[u]}$ when that happens (we don't care what $a_v$ and $c_v$ were before this).↵

But how do we find the root of a component?↵

$root_u$ is the lowest ancestor of $u$ such that the path from $u$ to $root_u$ contains no deactivated edges. We can thus use the same idea we used for the previous problem, but this time, all edges initially have their weight equal to 1 instead of 0.↵

Using binary lifting, we can find the root of any component in $O(\log^2 N)$ time.↵

This solution runs in $O(M \log^2 N)$ time
.↵

<spoiler summary="My code for this problem">↵
```cpp↵
#include <bits/stdc++.h>↵
#define FOR(i, x, y) for (int i = x; i < y; i++)↵
typedef long long ll;↵
using namespace std;↵

int n, m, q;↵
bool active[100001];↵
vector<int> graph[100001];↵
pair<int, int> edges[200001];↵

int info[100001], last_sync[100001];↵

int timer = 1, tin[100001], tout[100001];↵
int anc[100001][20];↵

void dfs(int node = 1, int parent = 0) {↵
    anc[node][0] = parent;↵
    for (int i = 1; i < 20 && anc[node][i - 1]; i++) {↵
        anc[node][i] = anc[anc[node][i - 1]][i - 1];↵
    }↵

    info[node] = 1;↵

    tin[node] = timer++;↵
    for (int i : graph[node]) if (i != parent) dfs(i, node);↵
    tout[node] = timer;↵
}↵

int bit[100001];↵

void update(int pos, int val) { for (; pos <= n; pos += (pos & (-pos))) bit[pos] += val; }↵

int query(int pos) {↵
    int ans = 0;↵
    for (; pos; pos -= (pos & (-pos))) ans += bit[pos];↵
    return ans;↵
}↵

int find_ancestor(int node) {↵
    int lca = node;↵
    for (int i = 19; ~i; i--) {↵
        if (anc[lca][i] && query(tin[anc[lca][i]]) == query(tin[node])) lca = anc[lca][i];↵
    }↵
    return lca;↵
}↵

int main() {↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0);↵
    cin >> n >> m >> q;↵
    FOR(i, 1, n) {↵
        cin >> edges[i].first >> edges[i].second;↵
        graph[edges[i].first].push_back(edges[i].second);↵
        graph[edges[i].second].push_back(edges[i].first);↵
    }↵
    dfs();↵

    FOR(i, 1, n + 1) {↵
        update(tin[i], -1);↵
        update(tout[i], 1);↵
    }↵

    while (m--) {↵
        int x;↵
        cin >> x;↵
        int u = edges[x].first, v = edges[x].second;↵
        if (anc[u][0] == v) swap(u, v);↵

        if (active[x]) {↵
            info[v] = last_sync[v] = info[find_ancestor(u)];↵
            update(tin[v], -1);↵
            update(tout[v], 1);↵
        } else {↵
            info[find_ancestor(u)] += info[v] - last_sync[v];↵
            update(tin[v], 1);↵
            update(tout[v], -1);↵
        }↵
        active[x] = !active[x];↵
    }↵

    while (q--) {↵
        int x;↵
        cin >> x;↵
        cout << info[find_ancestor(x)] << '\n';↵
    }↵
    return 0;↵
}↵
```↵
</spoiler>↵

## Conclusion↵

I hope you've learned something from this tutorial. If anything is unclear, please let me know in the comments below.↵

## Additional problems↵

- [COCI 2020 Putovanje](https://oj.uz/problem/view/COCI20_putovanje)↵
- [JOI 2015 Railroad](https://joi2015ho.contest.atcoder.jp/tasks/joi2015ho_a) but on a general tree instead of a line↵
- [USACO 2015 Max Flow](http://www.usaco.org/index.php?page=viewproblem2&cpid=576)↵
- [SACO 2015 Towers](https://saco-evaluator.org.za/cms/sapo2015) (Doesn't use a Fenwick tree but has a similar idea)↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский dolphingarlic 2020-06-09 19:09:43 2161 Tiny change: 'hen apply our trick and solve' -> 'hen apply the above idea and solve' (published)
en2 Английский dolphingarlic 2020-06-09 18:10:34 667 Tiny change: 'initially 0. Support ' -> 'initially . Support '
en1 Английский dolphingarlic 2020-06-08 21:16:15 8031 Initial revision (saved to drafts)