읽기 전에 알아두면 좋아요
아래 개념이 익숙하면 본문을 바로 읽으세요. 낯선 개념만 링크에서 복습하면 됩니다.
- JavaScript 반복형 세그먼트 트리: 구간 합·단일 대입·결합 순서세그먼트 트리는 큰 구간을 작은 구간으로 나누어 저장하고 필요한 구간의 결과를 합치는 구조입니다. 단일 대입 뒤 부모 합을 갱신하고 구간을 결합합니다.
- JavaScript 배열: 인덱스 조회와 삽입·삭제 비용배열은 여러 값을 순서대로 담습니다. 인덱스로 값을 읽고 반복문으로 하나씩 살펴봅니다. 인덱스 접근과 배열을 순회할 때의 연산 비용을 확인합니다.
개념과 예제는 실행하지 않아도 읽을 수 있습니다. 내 컴퓨터·터미널에서 직접 실행하는 과정은 선택 실습입니다.
과정 위치와 선택 복습 안내
과정 위치: 심화 선택 실습 · 문제
과정 위치는 이 글이 속한 묶음입니다. 이 단계의 모든 개념을 먼저 읽을 필요는 없습니다. 위에 연결한 개념 중 낯선 내용만 복습하세요. 문제의 조건·상태·갱신 순서는 익숙한 언어로 설명하면 됩니다.
JavaScript로 문법·실행 복습하기 (선택)
개념 글의 코드는 JavaScript 예시입니다. 문제 화면에서는 JavaScript·Python·Java·C++·C# 중 익숙한 언어의 함수를 작성하세요. 본문의 Node.js 입출력 예시는 로컬 실행을 위한 별도 안내입니다.
세그먼트 트리 단일 대입·구간 합 문제는 배열에 대한 어떤 명령을 처리하나요?
배열의 값 대입과 구간 합 조회 명령을 처리하는 문제입니다. 배열·구간 합·트리의 기본을 준비하고, 아래 입력·반환 계약을 확인해 직접 풀어보세요.
적용 조건·범위: 입력은 위 계약을 만족한다고 가정합니다. 온라인 채점기는 제공하지 않으며 로컬 Node.js에서 JSON 입력으로 실행합니다.
[창작 문제] 전시실 예상 인원판 교체
전시실별 예상 인원을 한 칸씩 교체하며 구간 합계를 구합니다. replace는 증가량이 아니라 새로운 값을 지정합니다.
이 문제는 BlogFlow 자료구조 학습용으로 독립 창작했습니다. 외부 문제의 지문이나 테스트를 옮기지 않았습니다.
문제
가로로 놓인 전시실의 예상 인원판 values가 주어집니다. replace 작업은 한 칸의 예상치를 새 값으로 바꾸고, total 작업은 지정 구간의 예상치 합을 묻습니다. 변경이 즉시 다음 조회에 반영되도록 답하세요. 음수는 이전 예측에 대한 조정 결과를 나타낼 수 있으므로 허용합니다.
관련 구현 설명: JavaScript 반복형 세그먼트 트리: 구간 합·단일 대입·결합 순서
입력·출력과 제약
JSON 객체 {values,ops}. 작업은 [“replace”,index,value] 또는 [“total”,left,right]. 구간은 [left,right)입니다.
total 작업의 답을 순서대로 담은 JSON 배열입니다. 조회가 없으면 []입니다.
배열 길이와 작업 수는 각각 0~100,000입니다. 모든 값은 정수이고 절댓값 1,000,000 이하입니다. replace는 유효한 원소 인덱스만 사용하며 total은 0 ≤ left ≤ right ≤ n을 지킵니다. 모든 부분합은 안전한 정수 범위에 있습니다.
입력은 위 계약을 만족한다고 가정합니다. 온라인 채점기는 제공하지 않으며 로컬 Node.js에서 JSON 입력으로 실행합니다.
예시
예시 1 입력:
{"values":[4,2,7,1,3],"ops":[["total",1,5],["replace",2,5],["total",1,5],["total",0,0]]}예시 1 출력:
[13,11,0]예시 2 입력:
{"values":[],"ops":[]}예시 2 출력:
[]힌트
교체한 잎의 조상만 재계산하세요. 조회할 때 왼쪽과 오른쪽에서 수집한 블록을 서로 다른 누산기에 담으면 결합 순서가 보존됩니다.
정답과 해설
직접 풀어보기
먼저 선택한 언어의 입력·반환 계약에 맞춰 작성해 보세요. 힌트 받기와 정답과 비교하기는 코드를 실행하지 않는 AI 분석입니다. 해답·해설은 아래에서 필요할 때 펼칠 수 있습니다.
AI 힌트
코드를 실행한 채점 결과가 아닌 AI의 코드 분석입니다.
해답·해설 보기
function solution(values, ops) {
let base = 1;
while (base < values.length) base *= 2;
const tree = Array(base * 2).fill(0), out = [];
values.forEach((value, i) => {
tree[base + i] = value;
});
for (let i = base - 1; i > 0; i--) tree[i] = tree[i * 2] + tree[i * 2 + 1];
for (const[type, a, b] of ops) {
if (type === 'replace') {
let i = base + a;
tree[i] = b;
while ((i = Math.floor(i / 2)) > 0) tree[i] = tree[i * 2] + tree[i * 2 + 1];
} else {
let l = base + a, r = base + b, sum = 0;
while (l < r) {
if (l % 2) sum += tree[l++];
if (r % 2) sum += tree[-- r];
l = Math.floor(l / 2);
r = Math.floor(r / 2);
}
out.push(sum);
}
}
return out;
}
solution(values, ops)에 정수 배열과 [명령,정수,정수] 배열을 전달하여 total 합계의 숫자 배열을 반환합니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
def solution(values, ops):
base = 1
while base < len(values): base *= 2
tree = [0] * (base * 2)
tree[base:base + len(values)] = values
for i in range(base - 1, 0, -1): tree[i] = tree[i * 2] + tree[i * 2 + 1]
out = []
for kind, a, b in ops:
if kind == 'replace':
i = base + a
tree[i] = b
i //= 2
while i:
tree[i] = tree[i * 2] + tree[i * 2 + 1]
i //= 2
else:
left, right, total = base + a, base + b, 0
while left < right:
if left % 2: total += tree[left]; left += 1
if right % 2: right -= 1; total += tree[right]
left //= 2
right //= 2
out.append(total)
return out
solution(values, ops)에 정수 리스트와 [명령,정수,정수] 리스트를 전달하며 합계의 정수 리스트를 반환합니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
import java.util.*;
class Solution {
public List < Long > solution(long[] values, Object[][] ops) {
int base = 1;
while (base < values.length) base *= 2;
long[] tree = new long[base * 2];
System.arraycopy(values, 0, tree, base, values.length);
for (int i = base - 1; i > 0; i--) tree[i] = tree[i * 2] + tree[i * 2 + 1];
List < Long > out = new ArrayList < >();
for (Object[] op : ops) {
int a =((Number) op[1]).intValue();
long b =((Number) op[2]).longValue();
if (op[0].equals("replace")) {
int i = base + a;
tree[i] = b;
for (i /= 2; i > 0; i /= 2) tree[i] = tree[i * 2] + tree[i * 2 + 1];
} else {
int l = base + a, r = base +(int) b;
long sum = 0;
while (l < r) {
if ((l & 1) == 1) sum += tree[l++];
if ((r & 1) == 1) sum += tree[-- r];
l /= 2;
r /= 2;
}
out.add(sum);
}
}
return out;
}
}
Solution.solution(long[] values, Object[][] ops)는 List<Long>을 반환합니다. ops 행은 {"replace",index,value} 또는 {"total",left,right}이며 숫자는 Integer나 Long입니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
#include <algorithm>
#include <array>
#include <functional>
#include <list>
#include <limits>
#include <memory>
#include <numeric>
#include <queue>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
struct Op {
string type;
int a;
long long b;
};
vector < long long > solution(const vector < long long > & values, const vector < Op > & ops) {
int base = 1;
while (base < static_cast < int >(values.size())) base *= 2;
vector < long long > tree(base * 2, 0), out;
copy(values.begin(), values.end(), tree.begin() + base);
for (int i = base - 1; i > 0;-- i) tree[i] = tree[i * 2] + tree[i * 2 + 1];
for (const auto & op : ops) {
if (op.type == "replace") {
int i = base + op.a;
tree[i] = op.b;
for (i /= 2; i > 0; i /= 2) tree[i] = tree[i * 2] + tree[i * 2 + 1];
} else {
int l = base + op.a, r = base + static_cast < int >(op.b);
long long sum = 0;
while (l < r) {
if (l & 1) sum += tree[l++];
if (r & 1) sum += tree[-- r];
l /= 2;
r /= 2;
}
out.push_back(sum);
}
}
return out;
}
solution(values, ops)는 vector<long long> 합계를 반환합니다. values는 vector<long long>, ops는 vector<Op>이며 Op{type,a,b}의 a,b는 index,value 또는 left,right입니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
using System;
using System.Collections.Generic;
using System.Text;
public class Solution {
public List < long > Solve(long[] values, object[][] ops) {
int size = 1;
while (size < values.Length) size *= 2;
long[] tree = new long[size * 2];
Array.Copy(values, 0, tree, size, values.Length);
for (int i = size - 1; i > 0; i--) tree[i] = tree[i * 2] + tree[i * 2 + 1];
var result = new List < long >();
foreach(object[] op in ops) {
int a = Convert.ToInt32(op[1]);
long b = Convert.ToInt64(op[2]);
if ((string) op[0] == "replace") {
int i = size + a;
tree[i] = b;
for (i /= 2; i > 0; i /= 2) tree[i] = tree[i * 2] + tree[i * 2 + 1];
} else {
int l = size + a, r = size +(int) b;
long sum = 0;
while (l < r) {
if ((l & 1) == 1) sum += tree[l++];
if ((r & 1) == 1) sum += tree[-- r];
l /= 2;
r /= 2;
}
result.Add(sum);
}
}
return result;
}
}
Solution.Solve(long[] values, object[][] ops)는 List<long>을 반환합니다. 각 행은 new object[]{"replace",index,value} 또는 {"total",left,right}입니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
Node.js 24 CommonJS용 전체 풀이입니다. segment-tree-problem.cjs로 저장하세요. 클래스 선언, solve 함수, 표준 입력 처리가 모두 들어 있어 가이드 파일을 별도로 가져오지 않습니다. 예시 입력을 input.json에 저장하고 터미널에서 실행합니다.
Windows PowerShell:
Get-Content -Raw -Encoding UTF8 ./input.json | node ./segment-tree-problem.cjs
macOS / Linux:
node segment-tree-problem.cjs < input.jsonclass SegmentTree {
constructor(values, combine = (a, b) => a + b, identity = 0) {
if (!Array.isArray(values) || values.length > 1_000_000) {
throw new RangeError('길이 1,000,000 이하 배열이 필요합니다.');
}
if (typeof combine !== 'function') throw new TypeError('결합 함수가 필요합니다.');
this.n = values.length;
this.combine = combine;
this.identity = identity;
this.base = 1;
while (this.base < this.n) this.base *= 2;
this.tree = Array(this.base * 2).fill(identity);
for (let i = 0; i < this.n; i++) this.tree[this.base + i] = values[i];
for (let i = this.base - 1; i > 0; i--) {
this.tree[i] = combine(this.tree[i * 2], this.tree[i * 2 + 1]);
}
}
boundary(i) {
if (!Number.isInteger(i) || i < 0 || i > this.n) throw new RangeError('잘못된 경계입니다.');
}
set(index, value) {
this.boundary(index);
if (index === this.n) throw new RangeError('갱신 인덱스는 n보다 작아야 합니다.');
let p = this.base + index;
this.tree[p] = value;
while (p > 1) {
p = Math.floor(p / 2);
this.tree[p] = this.combine(this.tree[p * 2], this.tree[p * 2 + 1]);
}
}
query(left, right) {
this.boundary(left);
this.boundary(right);
if (left > right) throw new RangeError('left는 right 이하여야 합니다.');
let l = left + this.base, r = right + this.base;
let accLeft = this.identity, accRight = this.identity;
while (l < r) {
if (l % 2 === 1) accLeft = this.combine(accLeft, this.tree[l++]);
if (r % 2 === 1) accRight = this.combine(this.tree[--r], accRight);
l = Math.floor(l / 2);
r = Math.floor(r / 2);
}
return this.combine(accLeft, accRight);
}
}
function solve({ values, ops }) {
const tree = new SegmentTree(values), out = [];
for (const [type, a, b] of ops) {
if (type === 'replace') tree.set(a, b);
else if (type === 'total') out.push(tree.query(a, b));
else throw new Error('알 수 없는 작업입니다.');
}
return out;
}
module.exports = { solve };
if (require.main === module) {
const input = JSON.parse(require('node:fs').readFileSync(0, 'utf8'));
console.log(JSON.stringify(solve(input)));
}첫 total은 2+7+1+3=13입니다. replace 이후 원본은 [4,2,5,1,3]이므로 같은 구간은 11입니다. 마지막 조회는 빈 구간이므로 항등원 0을 출력합니다. solve는 세그먼트 트리를 한 번 만들고 replace를 set에, total을 query에 대응시킵니다. 새 예상치를 delta로 처리하지 않는 것이 Fenwick 증가 예제와 다른 점입니다.
base는 n 이상인 가장 작은 2의 거듭제곱입니다. 원본 values[i]는 tree[base+i]에 놓고 나머지 잎은 항등원으로 채웁니다. 각 내부 노드는 왼쪽 자식과 오른쪽 자식을 그 순서로 결합합니다. 따라서 루트는 패딩을 포함해도 실제 배열 전체와 같은 결과를 갖습니다.
조회는 l,r을 잎 위치로 옮긴 뒤 아직 처리하지 않은 [l,r) 영역을 좁힙니다. l이 오른쪽 자식이면 왼쪽 형제가 범위 밖이므로 tree[l]만 받아 l을 하나 늘립니다. r이 홀수이면 r−1이 범위 안의 마지막 왼쪽 자식이므로 먼저 r을 줄이고 그 노드를 받습니다. 나머지는 완전한 형제 쌍이라 부모로 올릴 수 있습니다.
빌드는 O(n+1), q개 작업은 최악 O(q log(n+2))이며 트리는 O(n+1), 결과는 O(q) 공간입니다. n=0에서 total(0,0)을 반복해도 각 질의와 출력 기록에 O(1)이 들어 전체 O(q) 비용이 남습니다. 숫자 합이 O(1)인 계약에서의 분석입니다.
표본과 경계를 직접 확인하려면 다음 코드를 segment-tree-check.cjs로 저장하고 같은 폴더에서 node segment-tree-check.cjs를 실행하세요. assert가 맞으면 출력 없이 종료하고, 다르면 예외와 함께 실패합니다.
const assert = require('node:assert/strict');
const { solve } = require('./segment-tree-problem.cjs');
assert.deepEqual(
solve({
"values": [
4,
2,
7,
1,
3
],
"ops": [
[
"total",
1,
5
],
[
"replace",
2,
5
],
[
"total",
1,
5
],
[
"total",
0,
0
]
]
}),
[13,11,0],
);
assert.deepEqual(
solve({
"values": [],
"ops": []
}),
[],
);연결 학습과 공식 자료
JavaScript 반복형 세그먼트 트리: 구간 합·단일 대입·결합 순서에서 연산별 이유와 전체 복잡도를 이어서 확인할 수 있습니다. 다른 형식의 공식 연습은 LeetCode 307 – Range Sum Query – Mutable를 참고하세요. 외부 문제의 정답이나 지문은 이 페이지에 복제하지 않았습니다.
공식 자료 확인일: 2026년 9월 10일. 구현은 이 글의 JavaScript 계약에 맞춰 독립적으로 작성했습니다. 다른 언어 라이브러리의 API와 숫자 범위가 그대로 적용되는 것은 아닙니다.
이 문제를 푼 뒤 확인하기
덧셈 갱신이 아닌 단일 대입일 때 이전 값을 제거하는지, 전체 구간 합을 다시 구해 보세요.
본문의 예제와 이 반례를 직접 실행해 예상 출력과 비교하고, 결과가 다르면 입력 조건과 반복 범위를 다시 확인하세요.
이 글이 도움이 되었나요?
이어서 공부하기
체크포인트: 해설을 가리고 다시 풀고, 경계 입력을 하나 바꾸어 예상 결과와 실제 결과를 비교하세요. 표본 하나에 더해 경계 입력과 작은 기준 풀이를 비교하고 왜 이 구조를 고르는지 설명하세요.
다음 추천 · 자료구조 개념: JavaScript LRU 캐시: Map과 이중 연결 리스트의 불변식
권장 순서는 학습 가이드와 같습니다. 다른 순서는 접힌 참고 목록에서 확인할 수 있습니다. 읽음 표시는 숙달이나 채점 결과가 아닙니다.
원래 과정 목록 순서 (선택)
읽음 기록
읽음 — / 전체 58개 · 필수 58개
새 글 받아보기
RSS 리더에서 BlogFlow의 새 글을 확인할 수 있습니다.
