글 읽기 - [c++] 느리게 갱신되는 세그먼트 트리 관련 질문이요

(追記) (追記ここまで)

[c++] 느리게 갱신되는 세그먼트 트리 관련 질문이요

10999번 - 구간 합 구하기 2

yejun0157 2년 전 0

제가 처음으로 "느리게 갱신되는 세그먼트 트리"를 이 문제로 구현을 해봤는데, 아래 코드에서 뭔가 계속 안 됩니다. 인터넷 다 뒤졌는데 문제점을 못 찾게겠더라고요. 살려주세요.

#include <iostream>
using namespace std;
typedef long long ll;
ll n, m, k;
ll a, b, c, d;
ll arr[1000100 * 4 + 1];
ll tree[1000100 * 4 + 1];
ll lazy[1000100 * 4 + 1];
ll init(ll s, ll e, ll node)
{
 if (s == e)
 {
 lazy[node] = 0;
 return tree[node] = arr[s];
 }
 ll mid = (s + e) / 2;
 return tree[node] = init(s, mid, node * 2) + init(mid + 1, e, node * 2 + 1);
}
void lazy_update(ll s, ll e, ll node)
{
 if (lazy[node])
 {
 tree[node] += (e - s + 1) * lazy[node];
 
 if (s != e)
 {
 lazy[node * 2] += lazy[node];
 lazy[node * 2 + 1] += lazy[node];
 }
 
 lazy[node] = 0;
 }
}
ll sum(ll s, ll e, ll l, ll r, ll node)
{
 lazy_update(s, e, node);
 
 if (e < l || s > r)
 {
 return 0;
 }
 
 if (s >= l && e <= r)
 {
 return tree[node];
 }
 
 ll mid = (s + e) / 2;
 
 return sum(s, mid, l, r, node * 2) + sum(mid + 1, e, l, r, node * 2 + 1);
}
ll update(ll s, ll e, ll l, ll r, ll node, ll val)
{
 lazy_update(s, e, node);
 
 if (e < l || s > r)
 {
 return tree[node];
 }
 
 if (s >= l && e <= r)
 {
 tree[node] += val;
 lazy_update(s, e, node);
 return tree[node];
 }
 
 ll mid = (s + e) / 2;
 
 return tree[node] = update(s, mid, l, r, node * 2, val) + update(mid + 1, e, l, r, node * 2 + 1, val);
}
int main()
{
 cin >> n >> m >> k;
 
 for (int i = 0; i < n; i++)
 {
 cin >> arr[i];
 }
 
 init(1, n, 1);
 
 for (int i = 0; i < m + k; i++)
 {
 cin >> a;
 
 if (a == 1)
 {
 cin >> b >> c >> d;
 
 update(1, n, b, c, 1, d);
 }
 else
 {
 cin >> b >> c;
 
 cout << sum(1, n, b, c, 1) << "\n";
 }
 }
}

pill27211 2년 전 0

1. 쿼리 요청은 베이스 인덱스를 1로 잡은 것처럼 쓰는데, 막상 입력은 0부터 받고 있습니다.

for (int i = 0; i < n; i++)

에서

for (int i = 1; i <= n; i++)

로

2. 지금과 같이 propagation()를 작성했을 때, 70행에서 val을 tree[node]에 더해주는 게 맞을까요 lazy[node]에 더해주는 게 맞을까요?

yejun0157 2년 전 0

아 lazy[node]에 val를 더해야 하는 군요! 감사합니다

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

[c++] 느리게 갱신되는 세그먼트 트리 관련 질문이요

yejun0157 2년 전 0

pill27211 2년 전 0

yejun0157 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말