0

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 :(

Deepak Tatyaji Ahire
  • 4,883
  • 2
  • 13
  • 35
Learpcs
  • 282
  • 3
  • 10
  • The semantics of the `update` function differs between the two versions you show. That means other parts of your code *also* have changed in between, which could account for the difference. Hard to say more without a proper [mre]. – Some programmer dude May 06 '22 at 11:02
  • 1
    These challenge/competitive coding web sites are mostly for highly skilled, experienced C++ hackers to spend some free time solving useless coding puzzles. Trying to learn C++ from them is like trying to learn ice-skating by playing a hockey game against a team consisting of Wayne Gretzky, Mario Lemiuex, Sidney Crosby, Mark Messier, Brian Leetch, and Phil Esposito. It's going to be far more productive to learn C++, first, using any number of reputable, edited, textbooks; and then try your luck at competitive coding or challenge/competition sites. – Sam Varshavchik May 06 '22 at 11:09
  • @SamVarshavchik I don't see where you coming from. I just tried to implement segment tree and wanted to see if it's correct on codeforces problem literally asking to implement segment tree. – Learpcs May 06 '22 at 11:26
  • Where I am coming from is simply this: what's asked there is really testing basic knowledge and understanding of computer science and algorithms. If someone don't know if it's correct, or not, a terse code review will not really help them understand anything, or learn anything. Instead, the correct answer here should be to go and learn the relevant areas of computer science and algorithms which are needed to implement this. Unfortunately, stackoverflow.com is not a replacement for a [good C++ and computer science algorithms textbook](https://stackoverflow.com/questions/388242/). – Sam Varshavchik May 06 '22 at 16:08
  • @SamVarshavchik You have a very strange point. You're telling me that I came up with a segment tree by myself and I should've looked in some book already? Or should just copy paste code from some book just because it's already been written somewhere? Can't I write code by myself? – Learpcs May 06 '22 at 18:49
  • Yes you can. In fact that's how most people learn C++, and the only way to learn the most complicated general purpose programming language in the world: one chapter at a time from a good C++ textbook, doing one practice example after another. The textbook explains all relevant concepts and material; and there's never a reason to search Google, watch random Youtube videos, read random blogs, or waste time on competitive coding/challenge/hacking sites that offer no learning material, whatsoever. I, and many others, manage to learn C++ without codeforces/hackerrank, et. al. Anyone else can too. – Sam Varshavchik May 06 '22 at 22:12

1 Answers1

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.

  1. 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.
Deepak Tatyaji Ahire
  • 4,883
  • 2
  • 13
  • 35
  • I don't understand problem with leaf node and updating before making recursive calls. My algorithm literally updates segments containing i-th element. If it was updated to bigger value then all segments containing i-th element will be increased to this value. Also if I reach the leaf node I also need to increase it to the same delta. In the second solution it is indeed crucial to assign `t[v]` before recursion calls, but that's not the case in the first solution. – Learpcs May 06 '22 at 19:03
  • Also testing first solution on some primitive test cases always leads to the right answer (or at least I didn't find some corner case) – Learpcs May 06 '22 at 19:04