<span data-docs-delta="[[20&#44; &quot;1、什么是线段树&quot;&#44; &quot;inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;uP1k\&quot;|32:2|direction:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;线段树是:&quot;&#44; &quot;0:\&quot;rgb(255%2C%200%2C%200)\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;利用分治思想处理对一段序列进行大量区间操作(区间修改、区间查询)的数据结构&quot;&#44; &quot;0:\&quot;rgb(255%2C%200%2C%200)\&quot;|10:1|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;0:\&quot;rgb(255%2C%200%2C%200)\&quot;|24:\&quot;S93S\&quot;|33:1|direction:\&quot;ltr\&quot;|list-id:\&quot;uT7T\&quot;|ordered:\&quot;ckj-decimal\&quot;&quot;]&#44; [20&#44; &quot;线段树可以在0(nlogn)的时间复杂度内，完成区间修改/区间查询操作。&quot;&#44; &quot;0:\&quot;rgb(255%2C%200%2C%200)\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;0:\&quot;rgb(255%2C%200%2C%200)\&quot;|24:\&quot;TgIX\&quot;|33:1|direction:\&quot;ltr\&quot;|list-id:\&quot;uT7T\&quot;|ordered:\&quot;ckj-decimal\&quot;&quot;]]" 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; &quot;2、线段树的拆分原理&quot;&#44; &quot;inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;qbNh\&quot;|32:2|direction:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;将[1&#44; n]分解成若干特定的子区间;&quot;&#44; &quot;inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;7BT9\&quot;|33:1|direction:\&quot;ltr\&quot;|list-id:\&quot;NQjk\&quot;|ordered:\&quot;decimal\&quot;&quot;]&#44; [20&#44; &quot;将每个区间[L&#44; R]都分解为少量特定的子区间&quot;&#44; &quot;inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;KZND\&quot;|33:1|direction:\&quot;ltr\&quot;|list-id:\&quot;NQjk\&quot;|ordered:\&quot;decimal\&quot;&quot;]&#44; [20&#44; &quot;通过对子区间的修改或统计，来实现快速对[L，R]区间的修改、统计。&quot;&#44; &quot;inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;aFHQ\&quot;|33:1|direction:\&quot;ltr\&quot;|list-id:\&quot;NQjk\&quot;|ordered:\&quot;decimal\&quot;&quot;]&#44; [30&#44; [{&quot;A1&quot;:[40&#44; [[20&#44; &quot;算法&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;Mn7O\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;sUcZ\&quot;|7:1&quot;]&#44; &quot;A2&quot;:[40&#44; [[20&#44; &quot;前缀和&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;WBOm\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;E8wb\&quot;|7:1&quot;]&#44; &quot;A3&quot;:[40&#44; [[20&#44; &quot;树状数组&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;TJH2\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;o3KE\&quot;|7:1&quot;]&#44; &quot;A4&quot;:[40&#44; [[20&#44; &quot;线段树&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;gS6a\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;T6P8\&quot;|7:1&quot;]&#44; &quot;B1&quot;:[40&#44; [[20&#44; &quot;区间求和&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;6DuN\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;g8E2\&quot;|7:1&quot;]&#44; &quot;B2&quot;:[40&#44; [[20&#44; &quot;√&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;fHcn\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;OHE7\&quot;|7:1&quot;]&#44; &quot;B3&quot;:[40&#44; [[20&#44; &quot;√&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;XYUc\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;Ybgr\&quot;|7:1&quot;]&#44; &quot;B4&quot;:[40&#44; [[20&#44; &quot;√&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;ov4m\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;Wdyw\&quot;|7:1&quot;]&#44; &quot;C1&quot;:[40&#44; [[20&#44; &quot;区间最值&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;Ie8V\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;AvmG\&quot;|7:1&quot;]&#44; &quot;C2&quot;:[40&#44; [[20&#44; &quot;×&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;IrAR\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;IERr\&quot;|7:1&quot;]&#44; &quot;C3&quot;:[40&#44; [[20&#44; &quot;√&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;0ohB\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;Gwsj\&quot;|7:1&quot;]&#44; &quot;C4&quot;:[40&#44; [[20&#44; &quot;√&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;okk3\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;N54J\&quot;|7:1&quot;]&#44; &quot;D1&quot;:[40&#44; [[20&#44; &quot;单点修改&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;48YT\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;EGjx\&quot;|7:1&quot;]&#44; &quot;D2&quot;:[40&#44; [[20&#44; &quot;×&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;ezLL\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;Quok\&quot;|7:1&quot;]&#44; &quot;D3&quot;:[40&#44; [[20&#44; &quot;√&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;kHis\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;3Eoo\&quot;|7:1&quot;]&#44; &quot;D4&quot;:[40&#44; [[20&#44; &quot;√&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;hqV2\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;1E0q\&quot;|7:1&quot;]&#44; &quot;E1&quot;:[40&#44; [[20&#44; &quot;区间修改&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;MVkG\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;Km1S\&quot;|7:1&quot;]&#44; &quot;E2&quot;:[40&#44; [[20&#44; &quot;×&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;Lhtc\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;k1EH\&quot;|7:1&quot;]&#44; &quot;E3&quot;:[40&#44; [[20&#44; &quot;×&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;urbn\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;8gge\&quot;|7:1&quot;]&#44; &quot;E4&quot;:[40&#44; [[20&#44; &quot;√&quot;&#44; &quot;26:\&quot;20775936\&quot;|inline-dir:\&quot;ltr\&quot;&quot;]&#44; [20&#44; &quot;\n&quot;&#44; &quot;24:\&quot;dAzH\&quot;|7:1|direction:\&quot;ltr\&quot;&quot;]]&#44; &quot;25:\&quot;WA9n\&quot;|7:1&quot;]}&#44; [[10&#44; 4&#44; &quot;26:\&quot;20775936\&quot;&quot;]]&#44; [[10&#44; 1&#44; &quot;26:\&quot;20775936\&quot;|3:124&quot;]&#44; [10&#44; 4&#44; &quot;26:\&quot;20775936\&quot;|3:123&quot;]]]&#44; &quot;25:\&quot;lJcWuB\&quot;|readOnly:false&quot;]]" 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>

二、线段树的性质小结

1. 建出来的并不一定是完全二叉树，而是具有完全二叉树性质;
2. 父结点为x，则左儿子为2x，右儿子为2x+1;
3. 如果区间长度为n，则:
1. 结点数量=2n-1，树的深度级别为log(n)的数量级，树的结点编号不超过4</em>n;
4. 线段树深度为h，则前h-1层是满二又树，最后一层可能不满;

//建树
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(r<p||l>p) 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]);
 }

//在下标为k的位置（对应区间[l, r]）
//查询范围是[x, y]
int query(int k, int l, int r, int x, int y){
  //如果当前区间完全在查询范围内
  if(x<=1&&y>=r) return a[k];
  int mid=l+r>>1;
  int res=0;
  //左一半有覆盖
  if(x<=mid) res=query(k*2, l, mid, x, y);
  //右一半有部分覆盖
  if(y>=mid+1) res=max(res, query(k*2+1, mid+1, r, x, y));
  return res;
  }