Remarks

I found what appears to actually, as surprising as it may be, be a bug in the AtCoder lazysegtree library, for which I filed https://github.com/atcoder/ac-library/issues/175. The sample cases below correspond to the ones mentioned in this issue. It was https://atcoder.jp/contests/abc351/tasks/abc351_e that brought to this. I suppose one can use the test cases of this AtCoder problem to test.

Problem

You are given an integer sequence $a_0,a1,\ldots,a{N-1}$ with length $N$. Process the following $Q$ queries in order:

0 $l$ $r$ $x$: $a_i \leftarrow a_i + x$ for $l \leq i < r$
1 $l$ $r$: Print $\sum_{i=l}^{r-1} a_i$

Constraint

$1 \leq N, Q \leq 5 \times 10^5$
$0 \leq a_i \leq 10^9$
$-10^9 \leq x \leq 10^9$
$0 \leq p < N$
$0 \leq l_i \leq r_i \leq N$

Sample cases

Input 1

Output 1

Input 2

Output 2

Concluding remarks

Considering how the AtCoder segment tree library is entirely generic, perhaps we can comprehensively test it across a large number and variety of segment tree problems. I was very surprised that AtCoder lazysegtree did not work for that problem. I initially thought that I was misusing it, but then, when I used another lazy segment tree library, it did work: https://atcoder.jp/contests/abc351/submissions/52896462.

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {

maspypy commented 3 months ago

On your implementation

I think Your implementation in https://github.com/atcoder/ac-library/issues/175 is just wrong, and it is not a bug of AtCoder Library.

As writtern in the document of lazy segtree of ACL: https://github.com/atcoder/ac-library/blob/master/document_en/lazysegtree.md $f(x\cdot y)=f(x)\cdot f(y)$ is needed. $f\colon x\mapsto x+c$ doesn't satisfy the condition.

I think the correct implementation looks like:

struct T {
  lint count, sum;
};

T op(T a, T b) { return {a.count + b.count, a.sum + b.sum}; }
T e() { return {0, 0}; }

T mapping(lint f, T x) { return {x.count, x.sum + f * x.count}; }
lint composition(lint f, lint g) { return f + g; }

We need to add $f$ to some aggregated data of a interval. If we keep only the sum, we can't find the resulted data. By keeping both count and sum, we can get the result.

maspypy commented 3 months ago

On the problem proposal

We can verify the lazysegtree implementation by the following problem. https://judge.yosupo.jp/problem/range_affine_range_sum

Furthermore, range add operation is a special case of range affine operation ($b=1$). So I think we don't need a new problem. However, we could consider adding it if there are new algorithms that need verification and cannot be tested in the existing problem.

If some hack cases are required, it should be added to range_affine_range_sum.

guoyiz23 commented 3 months ago

ごめんなさい、悪いです。どうもありがとう。

I got AC now. As for the machine translate generated above, I do not actually know Japanese other than the meaning of the Kanji, but AtCoder did inspire me to more seriously learn it. xD

私は実際に日本人とあまり話したことはありませんが、そのうち話すようになるかもしれません。

wangyingkuan commented 1 month ago

@guoyiz23 can you delete my commit in https://github.com/telegramdesktop/tdesktop/issues/26626#issuecomment-1807434346,a lot guys add my qq account ,is my bad.

yosupo06 / library-checker-problems

[Problem proposal] (Range Add Range Sum) #1137