const long long N = 2 * 1e5 + 2;

long long tree[4 * N], v[N];

void build(long long node, long long st, long long e)
{
    if (st == e)
    {
        tree[node] = v[st];
        return;
    }

    long long mid = (st + e) / 2;
    build(2 * node, st, mid);
    build(2 * node + 1, mid + 1, e);

    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

long long query(long long node, long long st, long long e, long long l, long long r)
{
    if (l > e || r < st)
        return 0;

    if (l <= st && r >= e)
        return tree[node];

    long long mid = (st + e) / 2;
    long long left = query(2 * node, st, mid, l, r);
    long long right = query(2 * node + 1, mid + 1, e, l, r);

    return left + right;
}

void update(long long node, long long st, long long e, long long ind, long long val)
{
    if (st == e)
    {
        v[st] = val;
        tree[node] = val;
        return;
    }

    long long mid = (st + e) / 2;
    if (ind <= mid)
    {
        update(2 * node, st, mid, ind, val);
    }
    else
    {
        update(2 * node + 1, mid + 1, e, ind, val);
    }

    tree[node] = (tree[2 * node] + tree[2 * node + 1]);
}