【警示后人】树状数组 WA on #8, #9, #10 的一种可能

P3384 【模板】重链剖分/树链剖分

uncesspath @ 2023-09-08 20:33:24

树状数组区间修改的方式是:

void upd(int l, int r, int v)
{
    upd(l, v);
    upd(r + 1, -v);
}

这里 -v 会是个负数,从而导致修改函数会用负数进行修改,取模的时候要 (x % p - y % p + p) % p 这样修改。


by luobo215 @ 2023-09-08 20:34:52

一定要%啊!!!


by C_ccx_N @ 2023-09-08 20:57:31

%


|