Chúng ta cần tính tổng các phần tử từ chỉ số i đến chỉ số j. Các truy vấn bao gồm các giá trị chỉ mục i và j sẽ được thực hiện nhiều lần.
Đầu vào:arr [] ={5, 6, 3, 4, 1} i =1, j =3 Đầu ra:13 Giải thích
6 + 3 + 4 =13sum [] ={5, 6 + 5, 3 + 6 + 5, 4 + 3 + 6 + 5, 1 + 4 + 3 + 6 + 5} sum [] ={5 , 11,14,18,19} sum [j] -sum [i-1] =sum [3] -sum [1-1] =sum [3] -sum [0] =18-5 =13
Logic rất cơ bản trong việc bắt đầu từ dạng vòng lặp i index đến j index và tổng hợp các phần tử giữa các chỉ mục đó. Nhưng chúng tôi không thể lưu trữ chúng trong biến phụ, vì vậy chúng tôi sẽ sử dụng một mảng khác, nơi chúng tôi thêm phần tử mảng với phần tử mảng cuối cùng, v.v. Và sau đó từ chỉ mục j, chúng ta sẽ trừ giá trị chỉ mục i-1;
Ví dụ
#include using namespace std; int rangeSum (int i, int j, int sum []) {if (i ==0) return sum [j]; return sum [j] - sum [i - 1];} int main () {int arr [] ={5, 6, 3, 4, 1}; int n =5; int sum [5]; sum [0] =arr [0]; for (int i =1; i Đầu ra
13