My segment tree update function doesn't work properly

Question

The problem:

In this task, you need to write a regular segment tree for the sum.

Input The first line contains two integers n and m (1≤n,m≤100000), the size of the array and the number of operations. The next line contains n numbers a_i, the initial state of the array (0≤a_i≤10^9). The following lines contain the description of the operations. The description of each operation is as follows:

1 i v: set the element with index i to v (0≤i<n, 0≤v≤10^9).
2 l r: calculate the sum of elements with indices from l to r−1 (0≤l<r≤n).
Output For each operation of the second type print the corresponding sum.

I'm trying to implement segment tree and all my functions works properly except for the update function:

void update(int i, int delta, int v = 0, int tl = 0, int tr = n - 1)
{
    if (tl == i && tr == i)
        t[v] += delta;
    else if (tl <= i && i <= tr)
    {
        t[v] += delta;
        int m = (tl + tr) / 2;
        int left = 2 * v + 1;
        int right = left + 1;
        update(i, delta, left, tl, m);
        update(i, delta, right, m + 1, tr);
    }
}

I got WA on segment tree problem, meanwhile with this update function I got accepted:

void update(int i, int new_value, int v = 0, int tl = 0, int tr = n - 1)
{
    if (tl == i && tr == i)
        t[v] = new_value;
    else if (tl <= i && i <= tr)
    {
        int m = (tl + tr) / 2;
        int left = 2 * v + 1;
        int right = left + 1;
        update(i, new_value, left, tl, m);
        update(i, new_value, right, m + 1, tr);
        t[v] = t[left] + t[right];
    }
}

I really don't understand why my first version is not working. I thought maybe I had some kind of overflowing problem and decided to change everything to long longs, but it didn't help, so the problem in the algorithm of updating itself. But it seems ok to me. For every segment that includes i I need to add sum of this segment to some delta (it can be negative, if for example I had number 5 and decided to change it to 3, then delta will be -2). So what's the problem? I really don't see it :(

Answer 1

There are 2 problems with your first solution:

1. The question expects you to do a point update. The condition (tl == i && tr == i) checks if you are the leaf node of the tree.

At leaf node, you have to actually replace the value instead of adding something into it, which you did for the second solution.

2. Secondly, you can only update the non-leaf nodes after all its child nodes are updated. Updating t[v] before making recursive call will anyways result into wrong answer.