CSES - Path Queries

Explanation: CPH 18.2

Time Complexity: $(N+Q)\log N$

Code: Assumes that dfs() code is included.

/**
 * Description: range sum queries and point updates for $D$ dimensions
 * Source: https://codeforces.com/blog/entry/64914
 * Verification: SPOJ matsum
 * Usage: \texttt{BIT<int,10,10>} gives 2D BIT
 * Time: O((\log N)^D)
 */

template <class T, int ...Ns> struct BIT {
    T val = 0; void upd(T v) { val += v; }