基础
建树
void build(int p, int l, int r)
{
t[p] = (tree){l, r, 0};
if (l == r)
{
t[p].sum = val[l];
return;
}
int mid = (l + r) >> 1;
build(lp, l, mid);
build(rp, mid + 1, r);
pushup(p);
}
单点修改（和）
void update(int p, int x, int k)
{
if (t[p].l == x && t[p].r == x)
{
t[p].sum += k;
return;
}
int mid = (t[p].l + t[p].r) >> 1;
if (x <= mid) update(lp, x, k);
if (x > mid) update(rp, x, k);
pushup(p);
}
区间修改 + lazy tag（和）
void pushdown(int p)
{
if (t[p].tag)
{
t[lp].sum += (t[lp].r - t[lp].l + 1) * t[p].tag;
t[rp].sum += (t[rp].r - t[rp].l + 1) * t[p].tag;
t[lp].tag += t[p].tag;
t[rp].tag += t[p].tag;
t[p].tag = 0;
}
}
void update(int p, int l, int r, ll k)
{
if (l <= t[p].l && t[p].r <= r)
{
t[p].sum += (ll)(t[p].r - t[p].l + 1) * k;
t[p].tag += k;
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid) update(lp, l, r, k);
if (r > mid) update(rp, l, r, k);
pushup(p);
}
区间查询（和）
int query(int p, int l, int r)
{
if (l <= t[p].l && t[p].r <= r)
return t[p].sum;
//pushdown(p); <--- 区间修改
int mid = (t[p].l + t[p].r) >> 1;
int ans = 0;
if (l <= mid) ans += query(lp, l, r);
if (r > mid) ans += query(rp, l, r);
return ans;
}
区间乘加 + 区间和查询
则线段树需要维护的节点信息有：区间和 \(sum\)，乘法和加法分别的懒标记 \(tag_{mul},~tag_{add}\)
此时讨论加法和乘法的优先级，push_up 仍为求和，考虑 push_down
- 当加法优先时
对于该节点 \(p\) ，有懒标记 \(p_m,~p_a\)，且有父节点 \(fa\)，懒标记 \(fa_m, ~fa_a\)
则对于 \(p\) 区间上的任意一个 \(x\)，要把它转化为和积的形式，有：
\[\begin{aligned}
x&=\{~[~(x+p_a)\times p_m ] + fa_a \} \times fa_m\\
&=(x\cdot p_m + p_a\cdot p_m + fa_a ) \times fa_m\\
&=x\cdot p_m \cdot fa_m + p_a\cdot p_m\cdot fa_m + fa_a\cdot fa_m\\
&= p_m\cdot fa_m~(x + p_a +\frac{fa_a}{p_m})
\end{aligned}
\]
得到新的 \(p^\prime_a = p_a +\frac{fa_a}{p_m},~ p^\prime_m = p_m\cdot fa_m\)，但是 \(p_a^\prime\) 可能不是整数，会损失精度，不成立。
- 当乘法优先时
同理有：
\[\begin{aligned}
x &= (x\cdot p_m + p_a)\times fa_m +fa_a\\
&= x\cdot p_m\cdot fa_m + p_a \cdot fa_m + fa_a
\end{aligned}
\]
得到新的 \(p^\prime_a = p_a \cdot fa_m + fa_a,~ p^\prime_m = p_m\cdot fa_m\) ，成立。
那么，得到乘法优先可行，考虑具体更新当前点 \(p\) 的区间 \([l,r]\)，则有：
\[\begin{aligned}
sum &= \sum\limits_{i=l}^r\Big(p_i\cdot p_m + p_a\Big)\\
&= \sum\limits_{i=l}^r p_i \cdot p_m + (r-l+1)\cdot p_a\\
&= sum\cdot p_m + (r-l+1)\cdot p_a
\end{aligned}
\]
void count(int p, ll m, ll a)
{
t[p].sum = (t[p].sum * m % mod + (t[p].r - t[p].l + 1) * a % mod) % mod;
t[p].mul = t[p].mul * m % mod;
t[p].add = (t[p].add * m % mod + a) % mod;
}
void pushdown(int p)
{
count(lp, t[p].mul, t[p].add);
count(rp, t[p].mul, t[p].add);
t[p].mul = 1;
t[p].add = 0;
}