계차 그룹

지금 배열 a 가 있어 요. [7]

int a[7];
a[0]=1;
a[1]=2;
a[2]=4;
a[3]=5;
a[4]=12
a[5]=34;
a[6]=123;
a[7]=3;

a [0] - a [4] 를 다 넣 으 려 면 가장 소박 한 방법 은

a[0]++;
a[1]++;
a[2]++;
a[3]++;
a[4]++;

시간 복잡 도 O (n) 타 자 를 쳐 도 힘 들 어 요.
하지만 신기 한 차이 점 그룹 d [7] 가 먼저 있 으 면 훨씬 절약 할 수 있 습 니 다!
지금 d [7] 를 엽 니 다.

int d[7];
d[0]=a[0];
d[1]=a[1]-a[0];
d[2]=a[2]-a[1];
d[3]=a[3]-a[2];
d[4]=a[4]-a[3];
d[5]=a[5]-a[4];
d[6]=a[6]-a[5];
d[7]=a[7]-a[6];

간단하게 할 수도 있어 요.

int d[7];
d[0]=a[0];
for(int i=1;i<=7;i++){
d[i]=a[i]-a[i-1];
}

차이 점 팀 완성!정말 멋지다!
차분 점 조 는 무엇 에 쓰 입 니까?
단일 지점 조회
우리 먼저 그것 의 규칙 을 봅 시다. 지금:
d
a
d[0]=1
a[0]=1
d[1]=1
a[1]=2
d[2]=2
a[2]=4
d[3]=1
a[3]=5
d[4]=7
a[4]=12
d[5]=22
a[5]=34
d[6]=89
a[6]=123
d[7]=-120
a[7]=3
a [0] = d [0];a[1]=d[1]+d[0]; a[2]=d[2]+d[1]+d[0]; … 이런 식 으로 유추 하 다
이렇게 하면 한 점 으로 조회 할 수 있다.
구간 수정
지금 a [0] - a [4] 를 수정 하려 면 d [0] + 1 (모든 a 에 d [0] 요소 가 있 음) 을 사용 한 다음 에 d [5] - 1 (a [5] 및 이후 의 숫자 에 d [5] 요소 가 있 음) a [0] [0] a [0] = d [1] + d [0] + d [0] + 1 a [2] = d [2] + d [1] + d [0] + d [0] + 1 a [0] + 1 a [3] = d [3] + d [3] + d [0] + 1 a [0] + 1 a [0] + 1 a [4] = d [4] + d [0] + 1 a [5] = d [5] = d [5] + [5] - 1] + d [0] + d [d [6] + d [5] - 1 +... + d [0] + 1 a [5] = d [7] + d [6] + d [5] - 1 +... + d [0]+ 1 차분 수조 의 시간 복잡 도 는 O (2) 구간 수정 으로 두 개의 단점 수정 이 되 고,
O (n) 가 O (2) 가 됐어 요.
단점
여러 번 조회 하고 너무 적 게 수정 하면 어떤 알고리즘 도 사용 하지 않 는 것 보다 시간 복잡 도가 높 을 수 있다 는 단점 을 말 하지 않 을 수 없다. 문 제 를 쓸 때 는 심사숙고 한 다음 에 해 야 한다. 꼭 사용 해 야 한다 면 트 리 배열 과 함께 사용 해 야 한다.
트 리 배열:https://blog.csdn.net/johnwayne0317/article/details/84927585