I have been trying to flatten the tree using euler tour and then making a segment tree on the value array for point update and range query . I cant seem to understand the logical error i am doing . Please someone guide.
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define fo(i, n) for (int i = 0; i < n; i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
int mod = (int)1e9 + 7;
const int INF = 1e18;
const int maxN = 2e5 + 1;
const int M = 20;
int t;
vector<int> tin(maxN, 0), tout(maxN, 0);
void dfs(int node, int par, vector<vector<int>> &v)
{
tin[node] = ++t;
for (auto child : v[node])
{
if (child != par)
{
dfs(child, node, v);
}
}
tout[node] = t;
}
struct segmenttree
{
int n;
// segment tree array
vector<int> st;
void init(int _n)
{
this->n = _n;
st.resize(4 * n, 0); // segmentree size <= 4*n always
}
// build the segment tree
void build(int start, int end, int node, vector<int> &v)
{
if (start == end)
{
st[node] = v[start];
return;
}
int mid = (start + end) / 2;
build(start, mid, 2 * node + 1, v);
build(mid + 1, end, 2 * node + 2, v);
st[node] = st[2 * node + 1] + st[2 * node + 2];
}
// query the segment tree
int query(int start, int end, int node, int l, int r)
{
// no overlap
if (start > r || end < l)
return 0;
// complete overlap
if (start >= l && end <= r)
return st[node];
// partial overlap
int mid = (start + end) / 2;
int p1 = query(start, mid, 2 * node + 1, l, r);
int p2 = query(mid + 1, end, 2 * node + 2, l, r);
return p1 + p2;
}
// update the segment tree
void update(int start, int end, int node, int idx, int val)
{
if (start == end)
{
st[node] = val;
return;
}
int mid = (start + end) / 2;
if (idx <= mid)
update(start, mid, 2 * node + 1, idx, val);
else
update(mid + 1, end, 2 * node + 2, idx, val);
st[node] = st[2 * node + 1] + st[2 * node + 2];
}
void build(vector<int> &v)
{
build(0, n — 1, 0, v);
}
int query(int l, int r)
{
return query(0, n — 1, 0, l, r);
}
void update(int x, int y)
{
update(0, n — 1, 0, x, y);
}
};
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
vector<vector<int>> v(n + 1);
vector<int> val(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> val[i];
}
for (int i = 2; i <= n; i++)
{
int x, y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
segmenttree st;
st.init(n + 1);
st.build(val);
t = 0;
dfs(1, 0, v);
vector<int> flat(n + 1);
for (int i = 1; i <= n; i++)
{
flat[tin[i]] = i;
}
for (int i = 0; i < q; i++)
{
int x;
cin >> x;
if (x == 1)
{
int s, value;
cin >> s >> value;
st.update(tin[s], value);
}
else
{
int s;
cin >> s;
int in = tin[s];
int out = tout[s];
cout << st.query(in, out) << endl;
}
}
return 0;
}