읽기 전에 알아두면 좋아요
아래 개념이 익숙하면 본문을 바로 읽으세요. 낯선 개념만 링크에서 복습하면 됩니다.
- JavaScript Fenwick Tree: lowbit로 구간 합과 단일 증가 갱신 구현펜윅 트리는 여러 구간의 합을 저장해 값이 바뀌어도 누적 합을 빠르게 갱신하는 구조입니다. lowbit 묶음과 값 대입을 증감 차이로 바꾸는 기준을 확인합니다.
- JavaScript 배열: 인덱스 조회와 삽입·삭제 비용배열은 여러 값을 순서대로 담습니다. 인덱스로 값을 읽고 반복문으로 하나씩 살펴봅니다. 인덱스 접근과 배열을 순회할 때의 연산 비용을 확인합니다.
개념과 예제는 실행하지 않아도 읽을 수 있습니다. 내 컴퓨터·터미널에서 직접 실행하는 과정은 선택 실습입니다.
과정 위치와 선택 복습 안내
과정 위치: 심화 선택 실습 · 문제
과정 위치는 이 글이 속한 묶음입니다. 이 단계의 모든 개념을 먼저 읽을 필요는 없습니다. 위에 연결한 개념 중 낯선 내용만 복습하세요. 문제의 조건·상태·갱신 순서는 익숙한 언어로 설명하면 됩니다.
JavaScript로 문법·실행 복습하기 (선택)
개념 글의 코드는 JavaScript 예시입니다. 문제 화면에서는 JavaScript·Python·Java·C++·C# 중 익숙한 언어의 함수를 작성하세요. 본문의 Node.js 입출력 예시는 로컬 실행을 위한 별도 안내입니다.
Fenwick Tree 구간 합 문제는 어떤 두 작업을 처리하고 무엇을 배열로 반환하나요?
값의 증가와 구간 합 조회 작업을 처리해 조회 결과 배열을 반환하는 문제입니다. 배열·인덱스·구간 합의 기본을 준비하고, 아래 입력·반환 계약을 확인해 직접 풀어보세요.
적용 조건·범위: 입력은 위 계약을 만족한다고 가정합니다. 온라인 채점기는 제공하지 않으며 로컬 Node.js에서 JSON 입력으로 실행합니다.
본문 근거: AtCoder Library 공식 Fenwick Tree 문서 · MDN Bitwise AND: Number의 32비트 변환
[창작 문제] 분산 선반의 보정 장부
처음 0인 선반별 수량 기록에 양수·음수 보정을 적용하고 반열린 구간의 순합을 계산합니다. 입력 값은 최종 값이 아니라 보정량입니다.
이 문제는 BlogFlow 자료구조 학습용으로 독립 창작했습니다. 외부 문제의 지문이나 테스트를 옮기지 않았습니다.
문제
전시 물품 보정 장부에는 n개 선반의 순증감 기록이 있으며 모두 0으로 시작합니다. add 작업은 한 선반에 보정량을 더합니다. sum 작업은 왼쪽 선반부터 오른쪽 경계 바로 전까지의 기록 합을 요청합니다. 순증감 장부이므로 값이 음수가 되어도 유효합니다. 모든 질의의 답을 순서대로 반환하세요.
관련 구현 설명: JavaScript Fenwick Tree: lowbit로 구간 합과 단일 증가 갱신 구현
입력·출력과 제약
JSON 객체 {n,ops}. 작업은 [“add”,index,delta] 또는 [“sum”,left,right]입니다. 구간은 [left,right)입니다.
sum 작업의 합계를 순서대로 담은 JSON 배열입니다. 빈 구간의 합은 0입니다.
0 ≤ n ≤ 100,000, 작업 수 0~100,000, 정수 보정량 |delta| ≤ 1,000,000. add는 0 ≤ index < n, sum은 0 ≤ left ≤ right ≤ n입니다. 이 제약에서 전체 보정량 절댓값 합은 10^11 이하라 Number 안전 정수 범위입니다.
입력은 위 계약을 만족한다고 가정합니다. 온라인 채점기는 제공하지 않으며 로컬 Node.js에서 JSON 입력으로 실행합니다.
예시
예시 1 입력:
{"n":4,"ops":[["add",0,3],["add",2,5],["sum",0,3],["add",2,-2],["sum",1,4],["sum",2,2]]}예시 1 출력:
[8,3,0]예시 2 입력:
{"n":0,"ops":[["sum",0,0]]}예시 2 출력:
[0]힌트
[left,right)의 합은 [0,right)의 합에서 [0,left)의 합을 빼면 됩니다. add의 인덱스만 내부에서 1을 더하세요.
정답과 해설
직접 풀어보기
먼저 선택한 언어의 입력·반환 계약에 맞춰 작성해 보세요. 힌트 받기와 정답과 비교하기는 코드를 실행하지 않는 AI 분석입니다. 해답·해설은 아래에서 필요할 때 펼칠 수 있습니다.
AI 힌트
코드를 실행한 채점 결과가 아닌 AI의 코드 분석입니다.
해답·해설 보기
function solution(n, ops) {
const tree = Array(n + 1).fill(0), out = [];
const prefix = end => {
let sum = 0;
for (let i = end; i > 0; i -= i & - i) sum += tree[i];
return sum;
};
for (const[type, a, b] of ops) {
if (type === 'add') {
for (let i = a + 1; i <= n; i += i & - i) tree[i] += b;
}
else out.push(prefix(b) - prefix(a));
}
return out;
}
solution(n, ops)에 선반 수와 [명령,정수,정수] 작업 배열을 전달하고 sum 결과 숫자 배열을 반환합니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
def solution(n, ops):
tree = [0] * (n + 1)
def prefix(end):
total = 0
while end > 0:
total += tree[end]
end -= end & -end
return total
out = []
for kind, a, b in ops:
if kind == 'add':
i = a + 1
while i <= n:
tree[i] += b
i += i & -i
else: out.append(prefix(b) - prefix(a))
return out
solution(n, ops)에 정수와 [명령,정수,정수] 리스트를 전달하며 sum 결과 정수 리스트를 반환합니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
import java.util.*;
class Solution {
private long prefix(long[] tree, int end) {
long sum = 0;
for (int i = end; i > 0; i -= i & - i) sum += tree[i];
return sum;
}
public List < Long > solution(int n, Object[][] ops) {
long[] tree = new long[n + 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("add")) {
for (int i = a + 1; i <= n; i += i & - i) tree[i] += b;
} else out.add(prefix(tree,(int) b) - prefix(tree, a));
}
return out;
}
}
Solution.solution(int n, Object[][] ops)는 List<Long>을 반환합니다. 각 행은 {"add",index,delta} 또는 {"sum",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(int n, const vector < Op > & ops) {
vector < long long > tree(n + 1, 0), out;
auto prefix = [&](int end) {
long long sum = 0;
for (int i = end; i > 0; i -= i & - i) sum += tree[i];
return sum;
};
for (const auto & op : ops) {
if (op.type == "add") {
for (int i = op.a + 1; i <= n; i += i & - i) tree[i] += op.b;
} else out.push_back(prefix(static_cast < int >(op.b)) - prefix(op.a));
}
return out;
}
solution(int n, const vector<Op>& ops)는 vector<long long>을 반환합니다. Op{type,a,b}의 a,b는 index,delta 또는 left,right입니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
using System;
using System.Collections.Generic;
using System.Text;
public class Solution {
private long Prefix(long[] tree, int end) {
long sum = 0;
for (int i = end; i > 0; i -= i & - i) sum += tree[i];
return sum;
}
public List < long > Solve(int n, object[][] ops) {
long[] tree = new long[n + 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] == "add") {
for (int i = a + 1; i <= n; i += i & - i) tree[i] += b;
} else result.Add(Prefix(tree,(int) b) - Prefix(tree, a));
}
return result;
}
}
Solution.Solve(int n, object[][] ops)는 List<long>을 반환합니다. 각 행은 new object[]{"add",index,delta} 또는 {"sum",left,right}입니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
Node.js 24 CommonJS용 전체 풀이입니다. fenwick-problem.cjs로 저장하세요. 클래스 선언, solve 함수, 표준 입력 처리가 모두 들어 있어 가이드 파일을 별도로 가져오지 않습니다. 예시 입력을 input.json에 저장하고 터미널에서 실행합니다.
Windows PowerShell:
Get-Content -Raw -Encoding UTF8 ./input.json | node ./fenwick-problem.cjs
macOS / Linux:
node fenwick-problem.cjs < input.jsonclass Fenwick {
constructor(n) {
if (!Number.isInteger(n) || n < 0 || n > 1_000_000) {
throw new RangeError('n은 0~1,000,000 정수여야 합니다.');
}
this.n = n;
this.tree = Array(n + 1).fill(0);
}
boundary(i) {
if (!Number.isInteger(i) || i < 0 || i > this.n) {
throw new RangeError('경계는 0~n 정수여야 합니다.');
}
}
add(index, delta) {
this.boundary(index);
if (index === this.n) throw new RangeError('갱신 인덱스는 n보다 작아야 합니다.');
if (!Number.isSafeInteger(delta)) throw new TypeError('증가량은 안전한 정수여야 합니다.');
for (let i = index + 1; i <= this.n; i += i & -i) {
this.tree[i] += delta;
}
}
prefix(end) {
this.boundary(end);
let sum = 0;
for (let i = end; i > 0; i -= i & -i) sum += this.tree[i];
return sum;
}
sum(left, right) {
this.boundary(left);
this.boundary(right);
if (left > right) throw new RangeError('left는 right 이하여야 합니다.');
return this.prefix(right) - this.prefix(left);
}
}
function solve({ n, ops }) {
const f = new Fenwick(n), out = [];
for (const [type, a, b] of ops) {
if (type === 'add') f.add(a, b);
else if (type === 'sum') out.push(f.sum(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)));
}처음 두 add 뒤 장부는 [3,0,5,0]입니다. [0,3)의 합은 8입니다. 2번 선반에 −2를 더하면 [3,0,3,0]이 되고 [1,4)의 합은 3입니다. [2,2)는 어떤 원소도 포함하지 않습니다. solve의 분기에서 add는 출력하지 않고 sum만 out에 추가하는 것이 출력 개수를 맞추는 핵심입니다.
내부 인덱스 i는 외부 index+1입니다. lowbit(i)=i & -i는 가장 낮은 1비트의 값입니다. tree[i]는 내부 [i−lowbit(i)+1,i]의 합을 저장합니다. i=6이면 lowbit=2이므로 내부 5,6번 두 원소의 합을 보관합니다. 같은 구간을 무작정 겹쳐 더하는 것이 아니라 질의 때 서로 겹치지 않게 선택합니다.
prefix(end)는 내부 i=end에서 시작합니다. tree[i]를 더한 뒤 i−=lowbit(i)로 방금 더한 블록을 건너뛰면 아직 더하지 않은 앞부분만 남습니다. 끝의 1비트를 하나씩 없애므로 O(log n)개 블록 뒤 0이 됩니다.
초기 배열은 O(n+1), q개 작업은 최악 O(q log(n+2))이며 구조 O(n+1)와 결과 O(q) 공간입니다. n=0이어도 유효한 sum(0,0) 요청마다 0을 기록하므로 q개의 요청 처리 비용은 O(q)입니다. 입력 JSON과 ops 자체도 O(q) 공간을 차지하며 스트리밍 입력 구현은 아닙니다.
표본과 경계를 직접 확인하려면 다음 코드를 fenwick-check.cjs로 저장하고 같은 폴더에서 node fenwick-check.cjs를 실행하세요. assert가 맞으면 출력 없이 종료하고, 다르면 예외와 함께 실패합니다.
const assert = require('node:assert/strict');
const { solve } = require('./fenwick-problem.cjs');
assert.deepEqual(
solve({
"n": 4,
"ops": [
[
"add",
0,
3
],
[
"add",
2,
5
],
[
"sum",
0,
3
],
[
"add",
2,
-2
],
[
"sum",
1,
4
],
[
"sum",
2,
2
]
]
}),
[8,3,0],
);
assert.deepEqual(
solve({
"n": 0,
"ops": [
[
"sum",
0,
0
]
]
}),
[0],
);연결 학습과 공식 자료
JavaScript Fenwick Tree: lowbit로 구간 합과 단일 증가 갱신 구현에서 연산별 이유와 전체 복잡도를 이어서 확인할 수 있습니다. 다른 형식의 공식 연습은 AtCoder B – Fenwick Tree를 참고하세요. 외부 문제의 정답이나 지문은 이 페이지에 복제하지 않았습니다.
공식 자료 확인일: 2026년 9월 10일. 구현은 이 글의 JavaScript 계약에 맞춰 독립적으로 작성했습니다. 다른 언어 라이브러리의 API와 숫자 범위가 그대로 적용되는 것은 아닙니다.
이 문제를 푼 뒤 확인하기
같은 위치를 두 번 갱신하는 경우와 한 원소만 포함하는 구간 합을 구해 보세요.
본문의 예제와 이 반례를 직접 실행해 예상 출력과 비교하고, 결과가 다르면 입력 조건과 반복 범위를 다시 확인하세요.
이 글이 도움이 되었나요?
이어서 공부하기
체크포인트: 해설을 가리고 다시 풀고, 경계 입력을 하나 바꾸어 예상 결과와 실제 결과를 비교하세요. 표본 하나에 더해 경계 입력과 작은 기준 풀이를 비교하고 왜 이 구조를 고르는지 설명하세요.
다음 추천 · 자료구조 개념: JavaScript 반복형 세그먼트 트리: 구간 합·단일 대입·결합 순서
권장 순서는 학습 가이드와 같습니다. 다른 순서는 접힌 참고 목록에서 확인할 수 있습니다. 읽음 표시는 숙달이나 채점 결과가 아닙니다.
원래 과정 목록 순서 (선택)
읽음 기록
읽음 — / 전체 58개 · 필수 58개
새 글 받아보기
RSS 리더에서 BlogFlow의 새 글을 확인할 수 있습니다.
