线段树模板

已结束 ACM/ICPC 开始于: 2025-1-22 19:00 100 小时 主持人: 1 
                            <span data-docs-delta="[[20&#44;  "1、什么是线段树"&#44;  "inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"uP1k\"|32:2|direction:\"ltr\""]&#44;  [20&#44;  "线段树是:"&#44;  "0:\"rgb(255%2C%200%2C%200)\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "利用分治思想处理对一段序列进行大量区间操作(区间修改、区间查询)的数据结构"&#44;  "0:\"rgb(255%2C%200%2C%200)\"|10:1|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "0:\"rgb(255%2C%200%2C%200)\"|24:\"S93S\"|33:1|direction:\"ltr\"|list-id:\"uT7T\"|ordered:\"ckj-decimal\""]&#44;  [20&#44;  "线段树可以在0(nlogn)的时间复杂度内，完成区间修改/区间查询操作。"&#44;  "0:\"rgb(255%2C%200%2C%200)\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "0:\"rgb(255%2C%200%2C%200)\"|24:\"TgIX\"|33:1|direction:\"ltr\"|list-id:\"uT7T\"|ordered:\"ckj-decimal\""]]" data-copy-origin="https://shimo.im">

1、什么是线段树

  1. 线段树是:利用分治思想处理对一段序列进行大量区间操作(区间修改、区间查询)的数据结构 
<ol start="2">
	<li class="" style="margin-bottom:0pt;margin-top:0pt;font-size:11pt;color:#494949;line-height:1.7;list-style-type:lower-alpha;">
		线段树可以在0(nlogn)的时间复杂度内，完成区间修改/区间查询操作。
	</li>
</ol>

	<span style="color:#494949;"><span style="font-size:14.6667px;"><span data-docs-delta="[[20&#44;  "2、线段树的拆分原理"&#44;  "inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"qbNh\"|32:2|direction:\"ltr\""]&#44;  [20&#44;  "将[1&#44;  n]分解成若干特定的子区间;"&#44;  "inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"7BT9\"|33:1|direction:\"ltr\"|list-id:\"NQjk\"|ordered:\"decimal\""]&#44;  [20&#44;  "将每个区间[L&#44;  R]都分解为少量特定的子区间"&#44;  "inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"KZND\"|33:1|direction:\"ltr\"|list-id:\"NQjk\"|ordered:\"decimal\""]&#44;  [20&#44;  "通过对子区间的修改或统计，来实现快速对[L，R]区间的修改、统计。"&#44;  "inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"aFHQ\"|33:1|direction:\"ltr\"|list-id:\"NQjk\"|ordered:\"decimal\""]&#44;  [30&#44;  [{"A1":[40&#44;  [[20&#44;  "算法"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"Mn7O\"|7:1|direction:\"ltr\""]]&#44;  "25:\"sUcZ\"|7:1"]&#44;  "A2":[40&#44;  [[20&#44;  "前缀和"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"WBOm\"|7:1|direction:\"ltr\""]]&#44;  "25:\"E8wb\"|7:1"]&#44;  "A3":[40&#44;  [[20&#44;  "树状数组"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"TJH2\"|7:1|direction:\"ltr\""]]&#44;  "25:\"o3KE\"|7:1"]&#44;  "A4":[40&#44;  [[20&#44;  "线段树"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"gS6a\"|7:1|direction:\"ltr\""]]&#44;  "25:\"T6P8\"|7:1"]&#44;  "B1":[40&#44;  [[20&#44;  "区间求和"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"6DuN\"|7:1|direction:\"ltr\""]]&#44;  "25:\"g8E2\"|7:1"]&#44;  "B2":[40&#44;  [[20&#44;  "√"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"fHcn\"|7:1|direction:\"ltr\""]]&#44;  "25:\"OHE7\"|7:1"]&#44;  "B3":[40&#44;  [[20&#44;  "√"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"XYUc\"|7:1|direction:\"ltr\""]]&#44;  "25:\"Ybgr\"|7:1"]&#44;  "B4":[40&#44;  [[20&#44;  "√"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"ov4m\"|7:1|direction:\"ltr\""]]&#44;  "25:\"Wdyw\"|7:1"]&#44;  "C1":[40&#44;  [[20&#44;  "区间最值"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"Ie8V\"|7:1|direction:\"ltr\""]]&#44;  "25:\"AvmG\"|7:1"]&#44;  "C2":[40&#44;  [[20&#44;  "×"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"IrAR\"|7:1|direction:\"ltr\""]]&#44;  "25:\"IERr\"|7:1"]&#44;  "C3":[40&#44;  [[20&#44;  "√"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"0ohB\"|7:1|direction:\"ltr\""]]&#44;  "25:\"Gwsj\"|7:1"]&#44;  "C4":[40&#44;  [[20&#44;  "√"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"okk3\"|7:1|direction:\"ltr\""]]&#44;  "25:\"N54J\"|7:1"]&#44;  "D1":[40&#44;  [[20&#44;  "单点修改"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"48YT\"|7:1|direction:\"ltr\""]]&#44;  "25:\"EGjx\"|7:1"]&#44;  "D2":[40&#44;  [[20&#44;  "×"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"ezLL\"|7:1|direction:\"ltr\""]]&#44;  "25:\"Quok\"|7:1"]&#44;  "D3":[40&#44;  [[20&#44;  "√"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"kHis\"|7:1|direction:\"ltr\""]]&#44;  "25:\"3Eoo\"|7:1"]&#44;  "D4":[40&#44;  [[20&#44;  "√"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"hqV2\"|7:1|direction:\"ltr\""]]&#44;  "25:\"1E0q\"|7:1"]&#44;  "E1":[40&#44;  [[20&#44;  "区间修改"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"MVkG\"|7:1|direction:\"ltr\""]]&#44;  "25:\"Km1S\"|7:1"]&#44;  "E2":[40&#44;  [[20&#44;  "×"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"Lhtc\"|7:1|direction:\"ltr\""]]&#44;  "25:\"k1EH\"|7:1"]&#44;  "E3":[40&#44;  [[20&#44;  "×"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"urbn\"|7:1|direction:\"ltr\""]]&#44;  "25:\"8gge\"|7:1"]&#44;  "E4":[40&#44;  [[20&#44;  "√"&#44;  "26:\"20775936\"|inline-dir:\"ltr\""]&#44;  [20&#44;  "\n"&#44;  "24:\"dAzH\"|7:1|direction:\"ltr\""]]&#44;  "25:\"WA9n\"|7:1"]}&#44;  [[10&#44;  4&#44;  "26:\"20775936\""]]&#44;  [[10&#44;  1&#44;  "26:\"20775936\"|3:124"]&#44;  [10&#44;  4&#44;  "26:\"20775936\"|3:123"]]]&#44;  "25:\"lJcWuB\"|readOnly:false"]]" data-copy-origin="https://shimo.im">
	<h2 class="ql-long-20775936">
		<div data-header="2" ql-global-para="true" line="qbNh" class="ql-direction-ltr ql-long-20775936" data-foldable="true" data-default-linespacing="100" style="line-height:100%;font-size:14pt;">
			<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">2、线段树的拆分原理</span>
		</div>
	</h2>
	<ol start="2">
		<li class="" style="margin-bottom:0pt;margin-top:0pt;font-size:11pt;color:#494949;line-height:1.7;list-style-type:lower-alpha;">
			<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">将[1&#44;  n]分解成若干特定的子区间;</span>
		</li>
		<li class="" style="margin-bottom:0pt;margin-top:0pt;font-size:11pt;color:#494949;line-height:1.7;list-style-type:lower-alpha;">
			<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">将每个区间[L&#44;  R]都分解为少量特定的子区间</span>
		</li>
		<li class="" style="margin-bottom:0pt;margin-top:0pt;font-size:11pt;color:#494949;line-height:1.7;list-style-type:lower-alpha;">
			<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">通过对子区间的修改或统计，来实现快速对[L，R]区间的修改、统计。</span>
		</li>
	</ol>
	<table style="border-spacing:0px;">
		<tbody>
			<tr height="30" style="height:30px;">
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="sUcZ" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="124">
					<p align="center" line="Mn7O" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">算法</span>
					<br />
				</td>
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="g8E2" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="123">
					<p align="center" line="6DuN" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">区间求和</span>
					<br />
				</td>
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="AvmG" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="123">
					<p align="center" line="Ie8V" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">区间最值</span>
					<br />
				</td>
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="EGjx" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="123">
					<p align="center" line="48YT" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">单点修改</span>
					<br />
				</td>
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="Km1S" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="123">
					<p align="center" line="MVkG" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">区间修改</span>
					<br />
				</td>
			</tr>
			<tr height="30" style="height:30px;">
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="E8wb" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="124">
					<p align="center" line="WBOm" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">前缀和</span>
					<br />
				</td>
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="OHE7" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="123">
					<p align="center" line="fHcn" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">√</span>
					<br />
				</td>
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="IERr" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="123">
					<p align="center" line="IrAR" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">×</span>
					<br />
				</td>
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="Quok" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="123">
					<p align="center" line="ezLL" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">×</span>
					<br />
				</td>
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="k1EH" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="123">
					<p align="center" line="Lhtc" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">×</span>
					<br />
				</td>
			</tr>
			<tr height="30" style="height:30px;">
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="o3KE" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="124">
					<p align="center" line="TJH2" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">树状数组</span>
					<br />
				</td>
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="Ybgr" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="123">
					<p align="center" line="XYUc" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">√</span>
					<br />
				</td>
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="Gwsj" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="123">
					<p align="center" line="0ohB" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">√</span>
					<br />
				</td>
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="3Eoo" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="123">
					<p align="center" line="kHis" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">√</span>
					<br />
				</td>
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="8gge" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="123">
					<p align="center" line="urbn" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">×</span>
					<br />
				</td>
			</tr>
			<tr height="30" style="height:30px;">
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="T6P8" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="124">
					<p align="center" line="gS6a" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">线段树</span>
					<br />
				</td>
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="Wdyw" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="123">
					<p align="center" line="ov4m" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">√</span>
					<br />
				</td>
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="N54J" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="123">
					<p align="center" line="okk3" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">√</span>
					<br />
				</td>
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="1E0q" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="123">
					<p align="center" line="hqV2" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">√</span>
					<br />
				</td>
				<td spellcheck="false" autocorrect="off" autocomplete="off" class="ql-sheet-cell" rowspan="1" colspan="1" guid="WA9n" style="min-height:30px;border-width:1px;border-style:solid;vertical-align:top;padding:4px 0px;" width="123">
					<p align="center" line="dAzH" class="ql-align-center ql-direction-ltr" style="line-height:100%;margin-bottom:0pt;margin-top:0pt;text-align:center;font-size:11pt;color:#494949;">
						<span class="ql-author-20775936" inline-dir="ltr" ql-global="true">√</span>
					<br />
				</td>
			</tr>
		</tbody>
	</table>

</span></span></span><span data-docs-delta="[[30, [{"A1":[40, [[20, "算法", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"Mn7O"|7:1|direction:"ltr""]], "25:"sUcZ"|7:1"], "A2":[40, [[20, "前缀和", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"WBOm"|7:1|direction:"ltr""]], "25:"E8wb"|7:1"], "A3":[40, [[20, "树状数组", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"TJH2"|7:1|direction:"ltr""]], "25:"o3KE"|7:1"], "A4":[40, [[20, "线段树", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"gS6a"|7:1|direction:"ltr""]], "25:"T6P8"|7:1"], "B1":[40, [[20, "区间求和", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"6DuN"|7:1|direction:"ltr""]], "25:"g8E2"|7:1"], "B2":[40, [[20, "√", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"fHcn"|7:1|direction:"ltr""]], "25:"OHE7"|7:1"], "B3":[40, [[20, "√", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"XYUc"|7:1|direction:"ltr""]], "25:"Ybgr"|7:1"], "B4":[40, [[20, "√", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"ov4m"|7:1|direction:"ltr""]], "25:"Wdyw"|7:1"], "C1":[40, [[20, "区间最值", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"Ie8V"|7:1|direction:"ltr""]], "25:"AvmG"|7:1"], "C2":[40, [[20, "×", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"IrAR"|7:1|direction:"ltr""]], "25:"IERr"|7:1"], "C3":[40, [[20, "√", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"0ohB"|7:1|direction:"ltr""]], "25:"Gwsj"|7:1"], "C4":[40, [[20, "√", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"okk3"|7:1|direction:"ltr""]], "25:"N54J"|7:1"], "D1":[40, [[20, "单点修改", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"48YT"|7:1|direction:"ltr""]], "25:"EGjx"|7:1"], "D2":[40, [[20, "×", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"ezLL"|7:1|direction:"ltr""]], "25:"Quok"|7:1"], "D3":[40, [[20, "√", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"kHis"|7:1|direction:"ltr""]], "25:"3Eoo"|7:1"], "D4":[40, [[20, "√", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"hqV2"|7:1|direction:"ltr""]], "25:"1E0q"|7:1"], "E1":[40, [[20, "区间修改", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"MVkG"|7:1|direction:"ltr""]], "25:"Km1S"|7:1"], "E2":[40, [[20, "×", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"Lhtc"|7:1|direction:"ltr""]], "25:"k1EH"|7:1"], "E3":[40, [[20, "×", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"urbn"|7:1|direction:"ltr""]], "25:"8gge"|7:1"], "E4":[40, [[20, "√", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"dAzH"|7:1|direction:"ltr""]], "25:"WA9n"|7:1"]}, [[10, 4, "26:"20775936""]], [[10, 1, "26:"20775936"|3:124"], [10, 4, "26:"20775936"|3:123"]]], "25:"lJcWuB"|readOnly:false"], [20, {"gallery":"https://uploader.shimo.im/f/0s7J0KMDW1lIKtSM.png!thumbnail"}, "29:0|30:0|3:"1299"|4:"auto"|crop:""|frame:"none"|ori-height:"763"|ori-width:"1299""], [20, "\n", "24:"CU7S"|direction:"ltr""], [20, "\n", "24:"2YVW"|direction:"ltr""], [20, "二、线段树的性质小结", "inline-dir:"ltr""], [20, "\n", "24:"dICK"|32:1|direction:"ltr""], [20, {"gallery":"https://uploader.shimo.im/f/6PDWwBu2ESFWF5KC.png!thumbnail"}, "29:0|30:0|3:"2202"|4:"auto"|crop:""|frame:"none"|ori-height:"1065"|ori-width:"2202""], [20, "\n", "24:"cmLj"|direction:"ltr""], [20, "\n", "24:"Pda1"|direction:"ltr""], [20, "建出来的并不一定是完全二叉树，而是具有完全二叉树性质;", "inline-dir:"ltr""], [20, "\n", "24:"6oJr"|33:1|direction:"ltr"|list-id:"zcLc"|ordered:"decimal""], [20, "父结点为x，则左儿子为2x，右儿子为2x+1;", "inline-dir:"ltr""], [20, "\n", "24:"ecVN"|33:1|direction:"ltr"|list-id:"zcLc"|ordered:"decimal""], [20, "如果区间长度为n，则:", "inline-dir:"ltr""], [20, "\n", "24:"bJex"|33:1|direction:"ltr"|list-id:"zcLc"|ordered:"decimal""], [20, "结点数量=2n-1，树的深度级别为log(n)的数量级", "inline-dir:"ltr""], [20, "，树的结点编号不超过4n", "0:"rgb(255%2C%200%2C%200)"|inline-dir:"ltr""], [20, ";", "inline-dir:"ltr""], [20, "\n", "24:"r06f"|33:2|direction:"ltr"|list-id:"zcLc"|ordered:"decimal""], [20, "线段树深度为h，则前h-1层是满二又树，最后一层可能不满;", "inline-dir:"ltr""], [20, "\n", "24:"UwyB"|33:1|direction:"ltr"|list-id:"zcLc"|ordered:"decimal""]]" data-copy-origin="https://shimo.im">

 

二、线段树的性质小结


 

  1. 建出来的并不一定是完全二叉树，而是具有完全二叉树性质;
  2. 父结点为x，则左儿子为2x，右儿子为2x+1;
  3. 如果区间长度为n，则:
    1. 结点数量=2n-1，树的深度级别为log(n)的数量级，树的结点编号不超过4</em>n;
  4. 线段树深度为h，则前h-1层是满二又树，最后一层可能不满;
</span><span data-docs-delta="[[20, "三、线段树的构造", "inline-dir:"ltr""], [20, "\n", "24:"QcMI"|32:1|direction:"ltr""], [20, {"gallery":"https://uploader.shimo.im/f/CXQ71dYcLyqb4u45.png!thumbnail"}, "29:0|30:0|3:"1285"|4:"auto"|crop:""|frame:"none"|ori-height:"489"|ori-width:"1285""], [20, "\n", "24:"2ZBg"|direction:"ltr""], [20, "\n", "24:"B0wP"|direction:"ltr""], [30, [{"A1":[40, [[20, "1", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"vVBm"|7:1|direction:"ltr""]], "1:"%23a3e043"|25:"K9NY"|7:1"], "B1":[40, [[20, "2", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"erD9"|7:1|direction:"ltr""]], "1:"%23a3e043"|25:"PJIY"|7:1"], "C1":[40, [[20, "3", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"MaNN"|7:1|direction:"ltr""]], "1:"%23a3e043"|25:"q8KO"|7:1"], "D1":[40, [[20, "4", "26:"20775936"|inline-dir:"ltr""], [20, "\n", "24:"g65B"|7:1|direction:"ltr""]], "1:"%23a3e043"|25:"3pTO"|7:1"]}, [[10, 1, "26:"20775936""]], [[10, 4, "26:"20775936"|3:154"]]], "25:"iTGVd3"|readOnly:false"], [20, " 1 2 3 4 ", "inline-dir:"ltr""], [20, "\n", "24:"Vdg4"|direction:"ltr""], [20, "\n", "24:"bqFE"|direction:"ltr""], [30, [{"A1":[40, [[20, "\n", "24:"uMIC""]], "1:"%23e6b322"|25:"KBGf""], "B1":[40, [[20, "\n", "24:"hKmG""]], "1:"%23e6b322"|25:"Kzpr""], "C1":[40, [[20, "\n", "24:"OhPI""]], "1:"%23e6b322"|25:"JxbC""], "D1":[40, [[20, "\n", "24:"sBQ3""]], "1:"%23e6b322"|25:"hMOr""], "E1":[40, [[20, "\n", "24:"FFlO""]], "1:"%23e6b322"|25:"uNfm""], "F1":[40, [[20, "\n", "24:"WfUC""]], "1:"%23e6b322"|25:"eduW""], "G1":[40, [[20, "\n", "24:"zZf0""]], "1:"%23e6b322"|25:"IsBx""]}, [[10, 1, "26:"20775936""]], [[10, 7, "26:"20775936"|3:88"]]], "25:"ecvUxM"|readOnly:false"], [20, " 1 2 3 4 5 6 7", "inline-dir:"ltr""], [20, "\n", "24:"f8CU"|direction:"ltr""], [20, "\n", "24:"5MBN"|direction:"ltr""], [20, "//建树"], [20, "\n", "24:"nFmA"|36:22|direction:"ltr""], [20, "void build(int k, int l, int r){"], [20, "\n", "24:"P8ID"|36:22|direction:"ltr""], [20, "//如果是叶子节点"], [20, "\n", "24:"l0qu"|36:22|direction:"ltr""], [20, " if(lr){"], [20, "\n", "24:"KEYY"|36:22|direction:"ltr""], [20, " ma[k]=a[i];"], [20, "\n", "24:"C9tD"|36:22|direction:"ltr""], [20, " return;"], [20, "\n", "24:"6XbU"|36:22|direction:"ltr""], [20, " "], [20, "\n", "24:"xfg2"|36:22|direction:"ltr""], [20, " }"], [20, "\n", "24:"Bkgp"|36:22|direction:"ltr""], [20, " int mid=l+r>>1;"], [20, "\n", "24:"Yi8O"|36:22|direction:"ltr""], [20, " build(k2, l, mid); //构造左子树"], [20, "\n", "24:"YYVI"|36:22|direction:"ltr""], [20, " build(k2+1.mid+1, r); //构造右子树"], [20, "\n", "24:"fkgG"|36:22|direction:"ltr""], [20, " //利用字节点更新父节点"], [20, "\n", "24:"zy16"|36:22|direction:"ltr""], [20, " ma[k]=max(ma[k2], ma[k2+1]);"], [20, "\n", "24:"xqG9"|36:22|direction:"ltr""], [20, " "], [20, "\n", "24:"N4R8"|36:22|direction:"ltr""], [20, "}"], [20, "\n", "24:"SBCH"|36:22|direction:"ltr""], [20, "\n", "24:"oQgW"|direction:"ltr""], [20, "四、线段树的", "inline-dir:"ltr""], [20, "单点", "0:"rgb(255%2C%200%2C%200)"|inline-dir:"ltr""], [20, "修改", "inline-dir:"ltr""], [20, "\n", "24:"23LS"|32:1|direction:"ltr""], [20, {"gallery":"https://uploader.shimo.im/f/xrvAOgCJiVdT8s0z.png!thumbnail"}, "29:0|30:0|3:"1036"|4:"auto"|crop:""|frame:"none"|ori-height:"598"|ori-width:"1036""], [20, "\n", "24:"mupv"|direction:"ltr""], [20, {"gallery":"https://uploader.shimo.im/f/iBAh7uwzv2UnU878.png!thumbnail"}, "29:0|30:0|3:"1037"|4:"auto"|crop:""|frame:"none"|ori-height:"284"|ori-width:"1037""], [20, "\n", "24:"Vhky"|direction:"ltr""], [20, " //修改：将p点的值修改为v"], [20, "\n", "24:"nqY4"|36:22|direction:"ltr""], [20, " viod change(int k, int l, int r, int p, int v){"], [20, "\n", "24:"LBZ0"|36:22|direction:"ltr""], [20, " if(r<p||l>p) return;//当前区间完全不包含需要修改的点"], [20, "\n", "24:"RxJj"|36:22|direction:"ltr""], [20, " //叶结点，直接修改"], [20, "\n", "24:"XbZI"|36:22|direction:"ltr""], [20, " if(lp&&r==p){"], [20, "\n", "24:"mOXm"|36:22|direction:"ltr""], [20, " a[k]=v;"], [20, "\n", "24:"1gLw"|36:22|direction:"ltr""], [20, " return;"], [20, "\n", "24:"W6ml"|36:22|direction:"ltr""], [20, " } "], [20, "\n", "24:"qAdk"|36:22|direction:"ltr""], [20, " int mid=l+r>>1;"], [20, "\n", "24:"hdZ7"|36:22|direction:"ltr""], [20, " if(p<=mid) change(k2, mid, p, v)"], [20, "\n", "24:"EHfm"|36:22|direction:"ltr""], [20, " else change(k2+1, mid+1, r, p, v);"], [20, "\n", "24:"zerh"|36:22|direction:"ltr""], [20, " //回溯更新对应结点的值"], [20, "\n", "24:"bKKr"|36:22|direction:"ltr""], [20, " a[k]=max(a[k2], a[k2+1]);"], [20, "\n", "24:"fxkp"|36:22|direction:"ltr""], [20, " }"], [20, "\n", "24:"rIMs"|36:22|direction:"ltr""], [20, "五、线段树", "inline-dir:"ltr""], [20, "区间查询", "0:"rgb(255%2C%200%2C%200)"|inline-dir:"ltr""], [20, {"gallery":"https://uploader.shimo.im/f/TEDaaqGuIIb5RHNE.png!thumbnail"}, "29:0|30:0|3:"1229"|4:"auto"|crop:""|frame:"none"|ori-height:"712"|ori-width:"1229""], [20, "\n", "24:"6AAr"|32:1|direction:"ltr""], [20, "画图模拟查询", "inline-dir:"ltr""], [20, "\n", "24:"iUg5"|direction:"ltr""], [20, "query(1, 10) query(4, 6) ", "inline-dir:"ltr""], [20, "\n", "24:"nuPV"|direction:"ltr""], [20, "query(1, 5) query(4, 8) ", "inline-dir:"ltr""], [20, "\n", "24:"nmk4"|direction:"ltr""], [20, "query(4, 5) query(5, 6) ", "inline-dir:"ltr""], [20, "\n", "24:"IASG"|direction:"ltr""], [20, "\n", "24:"xTi2"|direction:"ltr""], [20, "左右区间包含需要的信息：", "inline-dir:"ltr""], [20, "\n", "24:"ayvg"|bullet-id:"IW4u"|bullet:"circle"|direction:"ltr""], [20, " x<=mid", "inline-dir:"ltr""], [20, "\n", "24:"NIZQ"|33:1|bullet-id:"6Hc9"|bullet:"circle"|direction:"ltr""], [20, "y>=mid+1", "inline-dir:"ltr""], [20, "\n", "24:"dOiE"|33:1|bullet-id:"6Hc9"|bullet:"circle"|direction:"ltr""], [20, "如果递归到的区间完全包含在查询区间：", "inline-dir:"ltr""], [20, "\n", "24:"kuKX"|bullet-id:"5hOh"|bullet:"circle"|direction:"ltr""], [20, "L>=x&&R<=y", "inline-dir:"ltr""], [20, "\n", "24:"2L2K"|33:1|bullet-id:"5hOh"|bullet:"circle"|direction:"ltr""], [20, "不需要再继续递归", "inline-dir:"ltr""], [20, "\n", "24:"1SAF"|33:1|bullet-id:"5hOh"|bullet:"circle"|direction:"ltr""], [20, "//在下标为k的位置（对应区间[l, r]）"], [20, "\n", "24:"aWme"|36:22|direction:"ltr""], [20, "//查询范围是[x, y]"], [20, "\n", "24:"jbdn"|36:22|direction:"ltr""], [20, "int query(int k, int l, int r, int x, int y){"], [20, "\n", "24:"8ddP"|36:22|direction:"ltr""], [20, " //如果当前区间完全在查询范围内"], [20, "\n", "24:"DaoB"|36:22|direction:"ltr""], [20, " if(x<=1&&y>=r) return a[k];"], [20, "\n", "24:"WcIh"|36:22|direction:"ltr""], [20, " int mid=l+r>>1;"], [20, "\n", "24:"wCsZ"|36:22|direction:"ltr""], [20, " int res=0;"], [20, "\n", "24:"7GIp"|36:22|direction:"ltr""], [20, " //左一半有覆盖"], [20, "\n", "24:"Etzr"|36:22|direction:"ltr""], [20, " if(x<=mid) res=query(k2, l, mid, x, y);"], [20, "\n", "24:"YyS7"|36:22|direction:"ltr""], [20, " //右一半有部分覆盖"], [20, "\n", "24:"MB4O"|36:22|direction:"ltr""], [20, " if(y>=mid+1) res=max(res, query(k2+1, mid+1, r, x, y));"], [20, "\n", "24:"WScf"|36:22|direction:"ltr""], [20, " return res;"], [20, "\n", "24:"d3ac"|36:22|direction:"ltr""], [20, " }"], [20, "\n", "24:"jaOF"|36:22|direction:"ltr""]]" data-copy-origin="https://shimo.im">

三、线段树的构造


 

1

2

3

4

1                                          2                                   3                                  4

 

 

 

 

 

 

 

 

1                           2                  3                 4                    5                  6              7 

  

//建树
void build(int k,  int l,  int r){
//如果是叶子节点
  if(l==r){
    ma[k]=a[i];
    return;
    
  }
  int mid=l+r>>1;
  build(k*2,  l,  mid);     //构造左子树
  build(k*2+1.mid+1,  r); //构造右子树
  //利用字节点更新父节点
  ma[k]=max(ma[k*2],  ma[k*2+1]);
  
}

 

四、线段树的单点修改 



 

//修改：将p点的值修改为v
 viod change(int k,  int l,  int r,  int p,  int v){
  if(rp) return;//当前区间完全不包含需要修改的点
  //叶结点，直接修改
  if(l==p&&r==p){
    a[k]=v;
    return;
  }   
  int mid=l+r>>1;
  if(p<=mid) change(k*2,  mid,  p,  v)
  else change(k*2+1,  mid+1,  r,  p,  v);
  //回溯更新对应结点的值
  a[k]=max(a[k*2],  a[k*2+1]);
 }

五、线段树区间查询

画图模拟查询

query(1, 10) query(4, 6)

query(1, 5) query(4, 8)

query(4, 5) query(5, 6)

 

  • 左右区间包含需要的信息：
    • x<=mid
    • y>=mid+1
  • 如果递归到的区间完全包含在查询区间：
    • L>=x&&R<=y 不需要再继续递归 
//在下标为k的位置（对应区间[l,  r]）
//查询范围是[x,  y]
int query(int k,  int l,  int r,  int x,  int y){
  //如果当前区间完全在查询范围内
  if(x=r) return a[k];
  int mid=l+r>>1;
  int res=0;
  //左一半有覆盖
  if(x=mid+1) res=max(res,  query(k*2+1,  mid+1,  r,  x,  y));
  return res;
  }
</span></span></span>

</span>

状态
已结束
规则
ACM/ICPC
题目
4
开始于
2025-1-22 19:00
结束于
2025-1-26 23:00
持续时间
100 小时
主持人
参赛人数
1
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 24ms
  4. Powered by Hydro v5.0.0-beta.4 Community