데이터 구조를 찾고 숫자를 연속적으로 추가하려면

-1

제목과 마찬가지로 숫자를 연속적으로 추가하려고합니다. 다음 예는 다음과 같습니다데이터 구조를 찾고 숫자를 연속적으로 추가하려면

enter image description here

나는 이것에 대한 데이터 구조가있다 preatty 확신하지만 그것이라고 기억하지 않습니다. 어떤 도움이라도 대단히 감사합니다. 감사.

출처

2014-09-02 Brian Moreno

[Fenwick tree] (https://en.wikipedia.org/wiki/Fenwick_tree)에 대해 묻는 것처럼 들립니다. – Sneftel

좀 더 자세히 설명해 주시겠습니까? 1에서 N까지 숫자를 합산하려고하십니까? 아니면 하위 영역을 추가하려고합니까? – templatetypedef

그래, 모든 숫자를 포괄적으로 추가하려고합니다. –

데이터 구조 질문보다 수학 문제가 더 중요하다고 생각합니다. :-)

숫자 1 + 2 + ... + n의 합계는 n (n + 1)/2와 같습니다.이 숫자를 n 번째 triangular number이라고합니다.

희망이 도움이됩니다.

출처

2014-09-02 22:47:43 templatetypedef

감사합니다. 나는 이것들에 대한 데이터 구조가 있다고 들었지만 이것 역시 효과가 있다고 생각한다. 도와 주셔서 다시 한 번 감사드립니다! :디 –

이 단순 합산 문제에 대한 데이터 구조는 과도한 것입니다. 숫자가 연속이면 이 드라이브를위한 최고의 공식입니다. 연속 시퀀스가 임의의 숫자 인 [8 9 10 11 12 13]에서 시작 되더라도 여전히 ((13 * (13 + 1))/2) - ((7 * (7 + 1))/2)으로 계산할 수 있습니다.

데이터 구조가 필요한 경우 Segment Tree을 사용하여 범위 합계를 계산할 수 있습니다. (데이터가 연속적이지 않을 때 가장 적합합니다.)

출처

2014-09-03 05:56:03

데이터 구조를 찾고 숫자를 연속적으로 추가하려면

답변

관련 문제