차이 점 그룹 학습 노트
자, 먼저 누 드 문 제 를 보 세 요. n 개의 숫자 가 있 습 니 다.
m 개 조작, 매번 조작, x ~ y 구간 의 모든 수 를 z 증가;
마지막 으로 q 개의 질문 이 있 습 니 다. 매번 질문 할 때마다 x ~ y 의 구간 과.
그럼 이 건 차분 팀 으로 이 루어 질 수 있 겠 네요.
차이 점 수 는 우수한 데이터 구조 일 뿐만 아니 라 좋 은 사상 이기 도 하 다.
차이 점 그룹의 기능 은 구간, 조회 점 을 수정 하 는 것 이다.
구간 을 수정 하 는 시간 복잡 도 는 O (1) 이 고 조회 점 의 시간 복잡 도 는 O (n) 이다.
어떻게 구체 적 으로 이 루어 졌 는 지 살 펴 보 겠 습 니 다.
여기 d 배열 이 필요 합 니 다. d [i] = a [i] - a [i - 1] 먼저 초기 화 해 야 합 니 다.
d[1]=a[1];
for(int i=2;i<=n;i++)
d[i]=a[i]-a[i-1];
그리고 처리 구간 입 니 다.
void update(int x,int y,int z)
{
d[x]+=z;
d[y+1]-=z;
}
어떻게 1 부터 n 까지 의 합 을 구 합 니까?다음은 O (n) 의 조회 입 니 다. 사실은 O (1) 의 조회 가 있 습 니 다. 접두사 와 만 구하 면 됩 니 다.
sum[1]=d[1];
for(int i=2;i<=n;i++)
sum[i]=sum[i-1]+d[i];
다음은 접두사 와 O (1) 를 구 하 는 것 입 니 다. 이때 sum 은 접두사 와
sum[1]=d[1];
t=a[1];
for(int i=2;i<=n;i++)
sum[i]+=sum[i-1]+d[i]+t,t+=d[i];
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JSON 입문 강좌 기초편 json 입문 학습 노트JSON: JavaScript Object Notation(JavaScript 객체 표현) JSON 인스턴스 JSON은 언어에 독립적: JSON은 Javascript 문법을 사용하여 데이터 대상을 설명하지만 JSON...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
