백준 구간 합 구하기 2042번 javascript

세그먼트 트리를 쓰면 해결할 수 있는 문제이다.

javascript 풀고 실행해보니

5%에서 에러가 뿜뿜 나는데 정신이 혼미해졌다.

반례 예시 찾아보니

1. 세그먼트 트리 범위

// N * 4로 많이 사용
const segmentTree = new Array(N * 4).fill(0);

2. 세그먼트 트리 업데이트 할 때 기존 배열에 값을 넣어줘야지 다음 업데이트 때 두 수의 차이를 반영할 수 있다

 const diff = BigInt(c) - arr[b - 1];
 // 아래 부분 추가
 arr[b - 1] = BigInt(c);

반례 찾아보고 돌려봤는데도 이상이 없어서

python으로 돌려봤는데 정답!

다시보니 정수 크기가 좀 컸다.

그래서 숫자들을 BigInt로 바꿔서 계산하니 정답이 되었다.

 

세그먼트 트리는 알고리즘 탭에 따로 글을 써볼 예정이다.

 

 

// https://www.acmicpc.net/problem/2042
const fs = require("fs");
const stdin = (
  process.platform === "linux"
    ? fs.readFileSync("/dev/stdin").toString()
    : `5 2 2
    1
    2
    3
    4
    5
    1 3 6
    2 2 5
    1 5 2
    2 3 5
`
).split("\n");

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const [N, M, K] = input()
  .trim()
  .split(" ")
  .map((v) => +v);

const arr = [];
const segmentTree = new Array(N * 4).fill(0);
for (let i = 0; i < N; i++) {
  arr.push(BigInt(input()));
}

const makeSegmentTree = (node, start, end) => {
  if (start === end) return (segmentTree[node] = arr[start]);
  const middle = Math.floor((start + end) / 2);
  const leftResult = makeSegmentTree(node * 2, start, middle);
  const rightResult = makeSegmentTree(node * 2 + 1, middle + 1, end);
  return (segmentTree[node] = BigInt(leftResult) + BigInt(rightResult));
};
const segmentTreeSum = (node, start, end, left, right) => {
  if (left > end || right < start) return 0;
  if (left <= start && right >= end) return segmentTree[node];
  const middle = Math.floor((start + end) / 2);
  const LeftSum = segmentTreeSum(node * 2, start, middle, left, right);
  const rightSum = segmentTreeSum(node * 2 + 1, middle + 1, end, left, right);
  return BigInt(LeftSum) + BigInt(rightSum);
};
const updateSegmentNode = (node, start, end, index, diff) => {
  if (index < start || index > end) return;
  segmentTree[node] += diff;
  if (start !== end) {
    const middle = Math.floor((start + end) / 2);
    updateSegmentNode(node * 2, start, middle, index, diff);
    updateSegmentNode(node * 2 + 1, middle + 1, end, index, diff);
  }
};
makeSegmentTree(1, 0, N - 1);
const answer = [];
for (let i = 0; i < M + K; i++) {
  const [a, b, c] = input()
    .trim()
    .split(" ")
    .map((v) => +v);
  if (a === 1) {
    const diff = BigInt(c) - arr[b - 1];
    arr[b - 1] = BigInt(c);
    updateSegmentNode(1, 0, N - 1, b - 1, diff);
    // console.log(segmentTree);
  } else {
    answer.push(segmentTreeSum(1, 0, N - 1, b - 1, c - 1));
  }
}
console.log(answer.join("\n"));

 

# https://www.acmicpc.net/problem/2042

import sys
input = sys.stdin.readline

N, M, K = map(int, input().strip().split(' '))

arr = []
segmentTree = [0]*(N * 4)
for i in range(N):
    arr.append(int(input()))


def makeSegmentTree(node, start, end):
    if (start == end):
        segmentTree[node] = arr[start]
        return segmentTree[node]
    middle = (start + end) // 2
    leftResult = makeSegmentTree(node * 2, start, middle)
    rightResult = makeSegmentTree(node * 2 + 1, middle + 1, end)
    segmentTree[node] = leftResult + rightResult
    return segmentTree[node]


def segmentTreeSum(node, start, end, left, right):
    if left > end or right < start:
        return 0
    if left <= start and right >= end:
        return segmentTree[node]
    middle = (start + end) // 2
    LeftSum = segmentTreeSum(node * 2, start, middle, left, right)
    rightSum = segmentTreeSum(node * 2 + 1, middle + 1, end, left, right)
    return LeftSum + rightSum


def updateSegmentNode(node, start, end, index, diff):
    if (index < start or index > end):
        return
    segmentTree[node] += diff
    if (start != end):
        middle = (start + end) // 2
        updateSegmentNode(node * 2, start, middle, index, diff)
        updateSegmentNode(node * 2 + 1, middle + 1, end, index, diff)


makeSegmentTree(1, 0, N - 1)
for i in range(M+K):
    a, b, c = map(int, input().strip().split(' '))
    if (a == 1):
        diff = c - arr[b - 1]
        arr[b - 1] = c
        updateSegmentNode(1, 0, N - 1, b - 1, diff)
    else:
        print(segmentTreeSum(1, 0, N - 1, b - 1, c - 1))