关于线段树左右区间长度的论证

算法

现象

int m = t[u]. r - t[u]. l + 1;
t[u << 1]. s = t[u]. lazy * (m - (m >> 1));
t[u << 1 | 1]. s = t[u]. lazy * (m >> 1);

证明

设区间左端点为$l$，右端点为$r$，中点为$mid$。

1. $\because\;$当区间长$X$为奇数，即$r-l+1\equiv 1\pmod{2}$时，有$r-l\equiv 0\pmod{2}$，
   $\therefore\;$必然存在$a\in N^*$使$l+2a=r$
   $\therefore\; mid=\lfloor\frac{l+r}{2}\rfloor=\lfloor\frac{l+(l+2a)}{2}\rfloor=l+a$
   $\therefore\;$左区间长$L=mid-l+1=(l+a)-l+1=a+1$
   $\quad$右区间长$R=r-mid=(l+2a)-(l+a)=a$
   $\quad$区间长$X=r-l+1=2a+1$
   $\therefore\;(X>>1)=\lfloor\frac{X}{2}\rfloor=a$
   $\quad\;(X-(X>>1))=X-\lfloor\frac{X}{2}\rfloor=a+1$
   $\therefore\;R=(X>>1),L=(X-(X>>1))$
2. $\because\;$当区间长$X$为偶数，即$r-l+1\equiv 0\pmod{2}$时，有$r-l\equiv 1\pmod{2}$，
   $\therefore\;$必然存在$a\in N^*$使$l+2a+1=r$
   $\therefore\; mid=\lfloor\frac{l+r}{2}\rfloor=\lfloor\frac{l+(l+2a+1)}{2}\rfloor=l+a$
   $\therefore\;$左区间长$L=mid-l+1=(l+a)-l+1=a+1$
   $\quad$右区间长$R=r-mid=(l+2a+1)-(l+a)=a+1$
   $\quad$区间长$X=r-l+1=2a+2$
   $\therefore\;(X>>1)=\lfloor\frac{X}{2}\rfloor=a+1$
   $\quad\;(X-(X>>1))=X-\lfloor\frac{X}{2}\rfloor=a+1$
   $\therefore\;R=(X>>1)=L=(X-(X>>1))$