-
2042, Gold 1백준 2021. 10. 7. 01:16
2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
문제
- 빈번하게 변하는 배열의 구간합을 구하시오
$O((m+k)log\ n)$
세그먼트 트리(Segment tree)를 재귀함수로 구현한다
※ 아래와 같이 구현할 때, 세그먼트 트리의 값을 담는 배열의 크기는 4*(다루는 숫자의 개수)
def init( ) ~ seg_i 의 값을 리턴
123456789ll init(int seg_i = 1, int arr_l = 1, int arr_r = n) // seg_i 값을 리턴{// leaf 노드일 경우if(arr_l == arr_r) return seg_tree[seg_i] = arr[arr_l];// leaf node 가 아닌경우int arr_m = (arr_l + arr_r)/2;return seg_tree[seg_i] = init(2*seg_i, arr_l, arr_m) + init(2*seg_i+1, arr_m+1, arr_r);}csdef update( ) ~ seg_i 의 값 수정(변화량 $delta$ 를 더해서 수정한다)
1234567891011121314// seg_i 값을 수정 if change_i 를 다루고 있는 경우<div class="colorscripter-code" style="color:#f0f0f0;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace !important; position:relative !important;overflow:auto"><table class="colorscripter-code-table" style="margin:0;padding:0;border:none;background-color:#272727;border-radius:4px;" cellspacing="0" cellpadding="0"><tr><td style="padding:6px;border-right:2px solid #4f4f4f"><div style="margin:0;padding:0;word-break:normal;text-align:right;color:#aaa;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace !important;line-height:130%"><div style="line-height:130%">1</div><div style="line-height:130%">2</div><div style="line-height:130%">3</div><div style="line-height:130%">4</div><div style="line-height:130%">5</div><div style="line-height:130%">6</div><div style="line-height:130%">7</div><div style="line-height:130%">8</div><div style="line-height:130%">9</div><div style="line-height:130%">10</div><div style="line-height:130%">11</div><div style="line-height:130%">12</div><div style="line-height:130%">13</div><div style="line-height:130%">14</div><div style="line-height:130%">15</div><div style="line-height:130%">16</div><div style="line-height:130%">17</div><div style="line-height:130%">18</div><div style="line-height:130%">19</div><div style="line-height:130%">20</div><div style="line-height:130%">21</div><div style="line-height:130%">22</div><div style="line-height:130%">23</div><div style="line-height:130%">24</div><div style="line-height:130%">25</div><div style="line-height:130%">26</div><div style="line-height:130%">27</div><div style="line-height:130%">28</div><div style="line-height:130%">29</div><div style="line-height:130%">30</div><div style="line-height:130%">31</div><div style="line-height:130%">32</div><div style="line-height:130%">33</div><div style="line-height:130%">34</div><div style="line-height:130%">35</div><div style="line-height:130%">36</div><div style="line-height:130%">37</div><div style="line-height:130%">38</div></div></td><td style="padding:6px 0;text-align:left"><div style="margin:0;padding:0;color:#f0f0f0;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace !important;line-height:130%"><div style="padding:0 6px; white-space:pre; line-height:130%">import sys</div><div style="padding:0 6px; white-space:pre; line-height:130%"> </div><div style="padding:0 6px; white-space:pre; line-height:130%">n, m, k <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> map(<span style="color:#4be6fa">int</span>, sys.stdin.readline().split())</div><div style="padding:0 6px; white-space:pre; line-height:130%">arr <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> [<span style="color:#c10aff">0</span>]</div><div style="padding:0 6px; white-space:pre; line-height:130%">seg_tree <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> [<span style="color:#c10aff">0</span>]<span style="color:#aaffaa"></span><span style="color:#ff3399">*</span>(<span style="color:#c10aff">4</span><span style="color:#ff3399">*</span>n)</div><div style="padding:0 6px; white-space:pre; line-height:130%"> </div><div style="padding:0 6px; white-space:pre; line-height:130%">def init(seg_i<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span><span style="color:#c10aff">1</span>, arr_l<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span><span style="color:#c10aff">1</span>, arr_r <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> n):</div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">if</span> arr_l <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span><span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> arr_r:</div><div style="padding:0 6px; white-space:pre; line-height:130%"> seg_tree[seg_i] <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> arr[arr_l]</div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">return</span> seg_tree[seg_i]</div><div style="padding:0 6px; white-space:pre; line-height:130%"> arr_m <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> (arr_l <span style="color:#aaffaa"></span><span style="color:#ff3399">+</span> arr_r)<span style="color:#999999">//2</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"> seg_tree[seg_i] <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> init(<span style="color:#c10aff">2</span><span style="color:#ff3399">*</span>seg_i, arr_l, arr_m) <span style="color:#aaffaa"></span><span style="color:#ff3399">+</span> init(<span style="color:#c10aff">2</span><span style="color:#ff3399">*</span>seg_i<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#c10aff">1</span>, arr_m<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#c10aff">1</span>, arr_r)</div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">return</span> seg_tree[seg_i]</div><div style="padding:0 6px; white-space:pre; line-height:130%"> </div><div style="padding:0 6px; white-space:pre; line-height:130%">def update(change_ind, delta, seg_i <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> <span style="color:#c10aff">1</span>, arr_l <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> <span style="color:#c10aff">1</span>, arr_r <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> n):</div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">if</span> change_ind <span style="color:#aaffaa"></span><span style="color:#ff3399"><</span> arr_l or arr_r <span style="color:#aaffaa"></span><span style="color:#ff3399"><</span> change_ind: <span style="color:#ff3399">return</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"> seg_tree[seg_i] <span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> delta</div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">if</span> arr_l <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span><span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> arr_r: <span style="color:#ff3399">return</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"> arr_m <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> (arr_l <span style="color:#aaffaa"></span><span style="color:#ff3399">+</span> arr_r)<span style="color:#999999">//2</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"> update(change_ind, delta, <span style="color:#c10aff">2</span><span style="color:#ff3399">*</span>seg_i, arr_l, arr_m)</div><div style="padding:0 6px; white-space:pre; line-height:130%"> update(change_ind, delta, <span style="color:#c10aff">2</span><span style="color:#ff3399">*</span>seg_i<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#c10aff">1</span>, arr_m<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#c10aff">1</span>, arr_r)</div><div style="padding:0 6px; white-space:pre; line-height:130%"> </div><div style="padding:0 6px; white-space:pre; line-height:130%">def sum_query(want_l, want_r, seg_i <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> <span style="color:#c10aff">1</span>, arr_l <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> <span style="color:#c10aff">1</span>, arr_r <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> n):</div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">if</span> want_r <span style="color:#aaffaa"></span><span style="color:#ff3399"><</span> arr_l or arr_r <span style="color:#aaffaa"></span><span style="color:#ff3399"><</span> want_l: <span style="color:#ff3399">return</span> <span style="color:#c10aff">0</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">if</span> want_l <span style="color:#aaffaa"></span><span style="color:#ff3399"><</span><span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> arr_l and arr_r <span style="color:#aaffaa"></span><span style="color:#ff3399"><</span><span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> want_r: <span style="color:#ff3399">return</span> seg_tree[seg_i]</div><div style="padding:0 6px; white-space:pre; line-height:130%"> arr_m <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> (arr_l <span style="color:#aaffaa"></span><span style="color:#ff3399">+</span> arr_r)<span style="color:#999999">//2</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">return</span> sum_query(want_l, want_r, <span style="color:#c10aff">2</span><span style="color:#ff3399">*</span>seg_i, arr_l, arr_m) <span style="color:#aaffaa"></span><span style="color:#ff3399">+</span> sum_query(want_l, want_r, <span style="color:#c10aff">2</span><span style="color:#ff3399">*</span>seg_i<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#c10aff">1</span>, arr_m<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#c10aff">1</span>, arr_r)</div><div style="padding:0 6px; white-space:pre; line-height:130%"> </div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#ff3399">for</span> i in range(n): arr.append(<span style="color:#4be6fa">int</span>(input()))</div><div style="padding:0 6px; white-space:pre; line-height:130%"> </div><div style="padding:0 6px; white-space:pre; line-height:130%">init()</div><div style="padding:0 6px; white-space:pre; line-height:130%"> </div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#ff3399">for</span> _ in range(m<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span>k):</div><div style="padding:0 6px; white-space:pre; line-height:130%"> a, b, c <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> map(<span style="color:#4be6fa">int</span>, sys.stdin.readline().split())</div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">if</span> a <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span><span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> <span style="color:#c10aff">1</span>:</div><div style="padding:0 6px; white-space:pre; line-height:130%"> update(b, c<span style="color:#aaffaa"></span><span style="color:#ff3399">-</span>arr[b])</div><div style="padding:0 6px; white-space:pre; line-height:130%"> arr[b] <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> c</div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">else</span>: print(sum_query(b, c))</div></div><div style="text-align:right;margin-top:-13px;margin-right:5px;font-size:9px;font-style:italic"><a href="http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter</a></div></td><td style="vertical-align:bottom;padding:0 2px 4px 0"><a href="http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white"><span style="font-size:9px;word-break:normal;background-color:#4f4f4f;color:white;border-radius:10px;padding:1px">cs</span></a></td></tr></table></div><div class="colorscripter-code" style="color:#f0f0f0;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace !important; position:relative !important;overflow:auto"><table class="colorscripter-code-table" style="margin:0;padding:0;border:none;background-color:#272727;border-radius:4px;" cellspacing="0" cellpadding="0"><tr><td style="padding:6px;border-right:2px solid #4f4f4f"><div style="margin:0;padding:0;word-break:normal;text-align:right;color:#aaa;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace !important;line-height:130%"><div style="line-height:130%">1</div><div style="line-height:130%">2</div><div style="line-height:130%">3</div><div style="line-height:130%">4</div><div style="line-height:130%">5</div><div style="line-height:130%">6</div><div style="line-height:130%">7</div><div style="line-height:130%">8</div><div style="line-height:130%">9</div><div style="line-height:130%">10</div><div style="line-height:130%">11</div><div style="line-height:130%">12</div><div style="line-height:130%">13</div><div style="line-height:130%">14</div><div style="line-height:130%">15</div><div style="line-height:130%">16</div><div style="line-height:130%">17</div><div style="line-height:130%">18</div><div style="line-height:130%">19</div><div style="line-height:130%">20</div><div style="line-height:130%">21</div><div style="line-height:130%">22</div><div style="line-height:130%">23</div><div style="line-height:130%">24</div><div style="line-height:130%">25</div><div style="line-height:130%">26</div><div style="line-height:130%">27</div><div style="line-height:130%">28</div><div style="line-height:130%">29</div><div style="line-height:130%">30</div><div style="line-height:130%">31</div><div style="line-height:130%">32</div><div style="line-height:130%">33</div><div style="line-height:130%">34</div><div style="line-height:130%">35</div><div style="line-height:130%">36</div><div style="line-height:130%">37</div><div style="line-height:130%">38</div></div></td><td style="padding:6px 0;text-align:left"><div style="margin:0;padding:0;color:#f0f0f0;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace !important;line-height:130%"><div style="padding:0 6px; white-space:pre; line-height:130%">import sys</div><div style="padding:0 6px; white-space:pre; line-height:130%"> </div><div style="padding:0 6px; white-space:pre; line-height:130%">n, m, k <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> map(<span style="color:#4be6fa">int</span>, sys.stdin.readline().split())</div><div style="padding:0 6px; white-space:pre; line-height:130%">arr <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> [<span style="color:#c10aff">0</span>]</div><div style="padding:0 6px; white-space:pre; line-height:130%">seg_tree <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> [<span style="color:#c10aff">0</span>]<span style="color:#aaffaa"></span><span style="color:#ff3399">*</span>(<span style="color:#c10aff">4</span><span style="color:#ff3399">*</span>n)</div><div style="padding:0 6px; white-space:pre; line-height:130%"> </div><div style="padding:0 6px; white-space:pre; line-height:130%">def init(seg_i<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span><span style="color:#c10aff">1</span>, arr_l<span style="color:#aaffaa"></span><span style="color:#ff3399">=</span><span style="color:#c10aff">1</span>, arr_r <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> n):</div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">if</span> arr_l <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span><span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> arr_r:</div><div style="padding:0 6px; white-space:pre; line-height:130%"> seg_tree[seg_i] <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> arr[arr_l]</div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">return</span> seg_tree[seg_i]</div><div style="padding:0 6px; white-space:pre; line-height:130%"> arr_m <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> (arr_l <span style="color:#aaffaa"></span><span style="color:#ff3399">+</span> arr_r)<span style="color:#999999">//2</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"> seg_tree[seg_i] <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> init(<span style="color:#c10aff">2</span><span style="color:#ff3399">*</span>seg_i, arr_l, arr_m) <span style="color:#aaffaa"></span><span style="color:#ff3399">+</span> init(<span style="color:#c10aff">2</span><span style="color:#ff3399">*</span>seg_i<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#c10aff">1</span>, arr_m<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#c10aff">1</span>, arr_r)</div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">return</span> seg_tree[seg_i]</div><div style="padding:0 6px; white-space:pre; line-height:130%"> </div><div style="padding:0 6px; white-space:pre; line-height:130%">def update(change_ind, delta, seg_i <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> <span style="color:#c10aff">1</span>, arr_l <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> <span style="color:#c10aff">1</span>, arr_r <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> n):</div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">if</span> change_ind <span style="color:#aaffaa"></span><span style="color:#ff3399"><</span> arr_l or arr_r <span style="color:#aaffaa"></span><span style="color:#ff3399"><</span> change_ind: <span style="color:#ff3399">return</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"> seg_tree[seg_i] <span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> delta</div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">if</span> arr_l <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span><span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> arr_r: <span style="color:#ff3399">return</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"> arr_m <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> (arr_l <span style="color:#aaffaa"></span><span style="color:#ff3399">+</span> arr_r)<span style="color:#999999">//2</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"> update(change_ind, delta, <span style="color:#c10aff">2</span><span style="color:#ff3399">*</span>seg_i, arr_l, arr_m)</div><div style="padding:0 6px; white-space:pre; line-height:130%"> update(change_ind, delta, <span style="color:#c10aff">2</span><span style="color:#ff3399">*</span>seg_i<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#c10aff">1</span>, arr_m<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#c10aff">1</span>, arr_r)</div><div style="padding:0 6px; white-space:pre; line-height:130%"> </div><div style="padding:0 6px; white-space:pre; line-height:130%">def sum_query(want_l, want_r, seg_i <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> <span style="color:#c10aff">1</span>, arr_l <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> <span style="color:#c10aff">1</span>, arr_r <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> n):</div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">if</span> want_r <span style="color:#aaffaa"></span><span style="color:#ff3399"><</span> arr_l or arr_r <span style="color:#aaffaa"></span><span style="color:#ff3399"><</span> want_l: <span style="color:#ff3399">return</span> <span style="color:#c10aff">0</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">if</span> want_l <span style="color:#aaffaa"></span><span style="color:#ff3399"><</span><span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> arr_l and arr_r <span style="color:#aaffaa"></span><span style="color:#ff3399"><</span><span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> want_r: <span style="color:#ff3399">return</span> seg_tree[seg_i]</div><div style="padding:0 6px; white-space:pre; line-height:130%"> arr_m <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> (arr_l <span style="color:#aaffaa"></span><span style="color:#ff3399">+</span> arr_r)<span style="color:#999999">//2</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">return</span> sum_query(want_l, want_r, <span style="color:#c10aff">2</span><span style="color:#ff3399">*</span>seg_i, arr_l, arr_m) <span style="color:#aaffaa"></span><span style="color:#ff3399">+</span> sum_query(want_l, want_r, <span style="color:#c10aff">2</span><span style="color:#ff3399">*</span>seg_i<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#c10aff">1</span>, arr_m<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span><span style="color:#c10aff">1</span>, arr_r)</div><div style="padding:0 6px; white-space:pre; line-height:130%"> </div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#ff3399">for</span> i in range(n): arr.append(<span style="color:#4be6fa">int</span>(input()))</div><div style="padding:0 6px; white-space:pre; line-height:130%"> </div><div style="padding:0 6px; white-space:pre; line-height:130%">init()</div><div style="padding:0 6px; white-space:pre; line-height:130%"> </div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#ff3399">for</span> _ in range(m<span style="color:#aaffaa"></span><span style="color:#ff3399">+</span>k):</div><div style="padding:0 6px; white-space:pre; line-height:130%"> a, b, c <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> map(<span style="color:#4be6fa">int</span>, sys.stdin.readline().split())</div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">if</span> a <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span><span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> <span style="color:#c10aff">1</span>:</div><div style="padding:0 6px; white-space:pre; line-height:130%"> update(b, c<span style="color:#aaffaa"></span><span style="color:#ff3399">-</span>arr[b])</div><div style="padding:0 6px; white-space:pre; line-height:130%"> arr[b] <span style="color:#aaffaa"></span><span style="color:#ff3399">=</span> c</div><div style="padding:0 6px; white-space:pre; line-height:130%"> <span style="color:#ff3399">else</span>: print(sum_query(b, c))</div></div><div style="text-align:right;margin-top:-13px;margin-right:5px;font-size:9px;font-style:italic"><a href="http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter</a></div></td><td style="vertical-align:bottom;padding:0 2px 4px 0"><a href="http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white"><span style="font-size:9px;word-break:normal;background-color:#4f4f4f;color:white;border-radius:10px;padding:1px">cs</span></a></td></tr></table></div>void update(int change_i, ll delta, int seg_i = 1, int arr_l = 1, int arr_r = n) // seg_i 값을 수정{if(change_i < arr_l || arr_r < change_i) return;seg_tree[seg_i] += delta;// leaf node 인 경우if(arr_l == arr_r) return;// leaf node 가 아닌경우int arr_m = (arr_l + arr_r)/2;update(change_i, delta, 2*seg_i, arr_l, arr_m);update(change_i, delta, 2*seg_i+1, arr_m+1, arr_r);}cs$seg_i$ 가 다루고 있는 index 이면 ($arr_l \leq change_i \leq arr_r$)
$seg_i$ 의 값을 바꾸어야 한다def sum_query( ) ~ seg_i 값 return if [arr_l, arr_r] ⊂ [want_l, want_r]
12345678910111213// seg_i 값 return if [arr_l, arr_r] ⊂ [want_l, want_r]ll sum_query(int want_l, int want_r, int seg_i = 1, int arr_l = 1, int arr_r = n){// 쓰레기 정보if(arr_r < want_l || want_r < arr_l) return 0;// 정보를 얻을 수 있고, 완전 다 필요해if(want_l <= arr_l && arr_r <= want_r) return seg_tree[seg_i];// 정보를 얻을 수 있으나, 쓰레기 정보 있네?int arr_m = (arr_l + arr_r)/2;return sum_query(want_l, want_r, 2*seg_i, arr_l, arr_m) + sum_query(want_l, want_r, 2*seg_i+1, arr_m+1, arr_r);}csseg_i 에서 구하려는 구간 $[want_l, want_r]$ 과 다루고 있는 index $[arr_l,\ arr_r]$ 을 비교할 때
i) 완전 다 쓰레기 정보
$want_r < arr_l\ or\ arr_r < want_l$ii) 정보를 얻을 수 있고, 완전 다 필요해
$want_l \leq arr_l \leq arr_r \leq want_r$iii) 정보를 얻을 수 있으나, 쓰레기 정보 있네?
그 외의 경우ex) 아래를 보면, 구간 [2, 5] 의 값을 더하려면 참조해야 하는 노트 색칠된 노드이다
c++
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#include <bits/stdc++.h>#define endl "\n"#define ooop(i, n) for(int i = 0; i < n; i++)#define loop(i, n) for(int i = 1; i <= n; i++)using namespace std;typedef long long ll;typedef pair<int, int> pii;typedef pair<ll, ll> pll;const int N = 1e6;ll arr[N+1];ll seg_tree[4*N];int n, m, k;ll init(int seg_i = 1, int arr_l = 1, int arr_r = n) // seg_i 값을 리턴{if(arr_l == arr_r) return seg_tree[seg_i] = arr[arr_l];int arr_m = (arr_l + arr_r)/2;return seg_tree[seg_i] = init(2*seg_i, arr_l, arr_m) + init(2*seg_i+1, arr_m+1, arr_r);}// seg_i 에는 [arr_l, arr_r]의 합을 저장하고 있다void update(int change_i, ll delta, int seg_i = 1, int arr_l = 1, int arr_r = n) // seg_i 값을 수정{if(change_i < arr_l || arr_r < change_i) return;seg_tree[seg_i] += delta;if(arr_l == arr_r) return;int arr_m = (arr_l + arr_r)/2;update(change_i, delta, 2*seg_i, arr_l, arr_m);update(change_i, delta, 2*seg_i+1, arr_m+1, arr_r);}ll sum_query(int want_l, int want_r, int seg_i = 1, int arr_l = 1, int arr_r = n) // sum([want_l, want_r] ∩ [arr_l, arr_r]){if(arr_r < want_l || want_r < arr_l) return 0;if(want_l <= arr_l && arr_r <= want_r) return seg_tree[seg_i];else{int arr_m = (arr_l + arr_r)/2;return sum_query(want_l, want_r, 2*seg_i, arr_l, arr_m) + sum_query(want_l, want_r, 2*seg_i+1, arr_m+1, arr_r);}}int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m >> k;loop(i, n) cin >> arr[i];init();m += k;while(m--){int a, b;ll c;cin >> a >> b >> c;if(a == 1) {update(b, c-arr[b]);arr[b] = c;}else cout << sum_query(b, c) << endl;}return 0;}cspython 3
1234567891011121314151617181920212223242526272829303132333435363738import sysn, m, k = map(int, sys.stdin.readline().split())arr = [0]seg_tree = [0]*(4*n)def init(seg_i=1, arr_l=1, arr_r = n):if arr_l == arr_r:seg_tree[seg_i] = arr[arr_l]return seg_tree[seg_i]arr_m = (arr_l + arr_r)//2seg_tree[seg_i] = init(2*seg_i, arr_l, arr_m) + init(2*seg_i+1, arr_m+1, arr_r)return seg_tree[seg_i]def update(change_ind, delta, seg_i = 1, arr_l = 1, arr_r = n):if change_ind < arr_l or arr_r < change_ind: returnseg_tree[seg_i] += deltaif arr_l == arr_r: returnarr_m = (arr_l + arr_r)//2update(change_ind, delta, 2*seg_i, arr_l, arr_m)update(change_ind, delta, 2*seg_i+1, arr_m+1, arr_r)def sum_query(want_l, want_r, seg_i = 1, arr_l = 1, arr_r = n):if want_r < arr_l or arr_r < want_l: return 0if want_l <= arr_l and arr_r <= want_r: return seg_tree[seg_i]arr_m = (arr_l + arr_r)//2return sum_query(want_l, want_r, 2*seg_i, arr_l, arr_m) + sum_query(want_l, want_r, 2*seg_i+1, arr_m+1, arr_r)for i in range(n): arr.append(int(input()))init()for _ in range(m+k):a, b, c = map(int, sys.stdin.readline().split())if a == 1:update(b, c-arr[b])arr[b] = c'백준' 카테고리의 다른 글
2515, 골드 2 (0) 2021.11.11 10999, Platinum 4 (0) 2021.10.08 16236, Gold 4 (0) 2021.10.03 11286, Silver 1 (0) 2021.10.03 15589, Gold 1 (0) 2021.10.03