# 线段树之懒惰标记

[x]-基本概念
[x]-懒惰标记
[ ]-……

## 【习题】线段树 2

1. 将某区间每一个数乘上 $x$
2. 将某区间每一个数加上 $x$
3. 求出某区间每一个数的和

### 题解

$$sum^\prime_0=sum^\prime_0\times\overbrace{1}^{lazymul_0} +\overbrace{0}^{lazyadd_0}\times span_0$$

\begin{aligned}sum_0=&\,(sum^\prime_0\times\overbrace{1}^{lazymul_0} +\overbrace{0}^{lazyadd_0}\times span_0+3\times span_0)\times4\\=&\,(sum^\prime_0\times\overbrace{1}^{lazymul_0} +\overbrace{3}^{lazyadd_0}\times span_0)\times4\\=&\,sum^\prime_0\times\overbrace{4}^{lazymul_0}+\overbrace{12}^{lazyadd_0}\times span_0\end{aligned}

\begin{aligned}sum_1&=\,(sum^\prime_1\times\overbrace{lazymul^\prime_1}^{lazymul_1}+\overbrace{lazyadd^\prime_1}^{lazyadd_1}\times span_1+3\times span_1)\times4\\&=\,[sum^\prime_1\times\overbrace{lazymul^\prime_1}^{lazymul_1} +\overbrace{(lazyadd^\prime_1+3)}^{lazyadd_1}\times span_1]\times4\\&=\, sum^\prime_1\times\overbrace{lazymul^\prime_1\times4}^{lazymul_1}+\overbrace{(lazyadd^\prime_1\times4+12)}^{lazyadd_1}\times span_1\\&=\, sum^\prime_1\times\overbrace{lazymul^\prime_1\times lazymul_0}^{lazymul_1} +\overbrace{(lazyadd^\prime_1\times lazymul_0+lazyadd_0)}^{lazyadd_1}\times span_1\end{aligned}

## 【习题】市场

1. 区间整体加上 $x$
2. 区间的每一个数除以 $x$，并向下取整
3. 查询区间最小值
4. 查询区间和