http://wiki.atp-fivt.org/index.php?action=history&feed=atom&title=%D0%9E%D0%B4%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%A4%D0%B5%D0%BD%D0%B2%D0%B8%D0%BA%D0%B0
Одномерное дерево Фенвика - История изменений
2026-04-11T04:12:04Z
История изменений этой страницы в вики
MediaWiki 1.30.0
http://wiki.atp-fivt.org/index.php?title=%D0%9E%D0%B4%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%A4%D0%B5%D0%BD%D0%B2%D0%B8%D0%BA%D0%B0&diff=274&oldid=prev
Algocourselecturenotes в 10:32, 4 апреля 2020
2020-04-04T10:32:40Z
<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="ru">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Версия 10:32, 4 апреля 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l14" >Строка 14:</td>
<td colspan="2" class="diff-lineno">Строка 14:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* легко обобщается на случай многомерных массивов.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* легко обобщается на случай многомерных массивов.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>=== Описание ===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>=== Описание ===</div></td></tr>
</table>
Algocourselecturenotes
http://wiki.atp-fivt.org/index.php?title=%D0%9E%D0%B4%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%A4%D0%B5%D0%BD%D0%B2%D0%B8%D0%BA%D0%B0&diff=273&oldid=prev
Algocourselecturenotes в 10:32, 4 апреля 2020
2020-04-04T10:32:29Z
<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="ru">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Версия 10:32, 4 апреля 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l12" >Строка 12:</td>
<td colspan="2" class="diff-lineno">Строка 12:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* использует ''O(n)'' дополнительной памяти</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* использует ''O(n)'' дополнительной памяти</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* легко обобщается на случай многомерных массивов.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* легко обобщается на случай многомерных массивов.</div></td></tr>
</table>
Algocourselecturenotes
http://wiki.atp-fivt.org/index.php?title=%D0%9E%D0%B4%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%A4%D0%B5%D0%BD%D0%B2%D0%B8%D0%BA%D0%B0&diff=272&oldid=prev
Algocourselecturenotes: Новая страница: «''Задача:'' Есть массив a<sub>0</sub> ... a<sub>n-1</sub>, хотим поддерживать операции: # '''upd''' (update) в одно…»
2020-04-04T10:31:59Z
<p>Новая страница: «''Задача:'' Есть массив a<sub>0</sub> ... a<sub>n-1</sub>, хотим поддерживать операции: # '''upd''' (update) в одно…»</p>
<p><b>Новая страница</b></p><div>''Задача:'' Есть массив a<sub>0</sub> ... a<sub>n-1</sub>, хотим поддерживать операции:<br />
# '''upd''' (update) в одной точке <br/> a<sub>pos</sub> += val<br />
# '''сумма на отрезке'''<br />
:::a<sub>l</sub> + ... + a<sub>r</sub> &ndash; ?<br />
<br />
== Дерево Фенвика ==<br />
'''Дерево Фенвика''' (англ. ''Binary Indexed Tree, BIT'') &ndash; это структура данных, дерево на массиве, обладающее следующими свойствами:<br />
<br />
* позволяет вычислять сумму на отрезке [l; r] за время ''O(log n)''<br />
<br />
* позволяет изменять значение любого элемента за ''O(log n)'' <br/> <br />
<br />
* использует ''O(n)'' дополнительной памяти<br />
<br />
<br />
* легко обобщается на случай многомерных массивов.<br />
<br />
<br />
=== Описание ===<br />
<br />
<br />
<!--(функция '''upd''' будет прибавлять к a<sub>pos</sub> на -a<sub>pos</sub> + a<sub>new</sub>)--></div>
Algocourselecturenotes