class segtree
{
public:
	vl seg;
	segtree(ll n)
	{
		seg = vl (4 * n + 2);
	}
	void build(ll ind, ll low, ll high, vl & v)
	{
		//build (ind,low,high)-->curr ind->ind of seg with range [low,high] for that
		//1.>write base case whether this range is leaf node or not if that then seg[ind]=a[low];
		//2.>build for the left child and build for the right child also
		//3.>calculate the work for (low,high) for curr ind


		// build-> work for[low,high] precomputed already
		// >base case->work for left and right childs-> work for curr ind
		if (low == high)
		{
			seg[ind] = v[low]; return;
		}

		ll mid = low + (high - low) / 2;
		build(2 * ind, low, mid, v);
		build((2 * ind) + 1, mid + 1, high, v);

		seg[ind] = seg[2 * ind] + seg[(2 * ind) + 1];
	}

// work[l, r] precomputed and stored
// query[l, r]->work[l, r] using some cases
// update(i, val)-> reach that range of seg and update there l = along with that kee upddaing fpr each parent also
	ll query(ll ind, ll low, ll high, ll l, ll r, vl & v)
	{
		//1.>no overlap with current ind, retur no work---[low,high][l,r]\\[l,r][low,high]
		if (high < l || r < low) return 0;//no work

		//2.>complete overlap-->-[l---low,high,---r]
		if (l <= low && high <= r)
		{
			return seg[ind];
		}

		//3.>partial overlap--->[low---l,r---high]
		ll mid = low + (high - low) / 2;
		ll left = query(2 * ind, low, mid, l, r, v);
		ll right = query((2 * ind) + 1, mid + 1, high, l, r, v);
		return (left + right);
		// t.c->O(k*logN)// worst cases me kuch se hi base pe jayega
	}

	void update(ll ind, ll low, ll high, ll i, ll val, vl & v)
	{
		//1.>base case when you reach the leaf node
		if (low == high)
		{
			seg[ind] = val; return;
		}

		//2.>call for either left and right
		ll mid = low + (high - low) / 2;
		if (i <= mid) update(2 * ind, low, mid, i, val, v);
		else update((2 * ind) + 1, mid + 1, high, i, val,  v);


		//3.>update this curr node also
		seg[ind] = seg[2 * ind] + seg[(2 * ind) + 1];
	}
};