An important part of a healthy life is getting enough exercise, and a popular way of measuring physical activity is by counting the number of steps we take. Suppose the number of steps taken for n consecutive days is stored in an array R, so that R[d] is the number of steps taken on day d (beginning with day O). We may be interested in looking at how many steps we took in total over span of days. In this problem we will build a structure to help us answer such queries efficiently. Assuming that 0 & R, int a, int b){ if (a == b) return R(a): else return R[b] + getSum(R, a, b-1); } What is the running time of getSum in the worst case? 0 (a) 8(n) O (b) (log n) O (c) en logro) 0 (d) (n) O (e) (1) Suppose we want to pre-compute the number of steps taken within any possible span of days. Exactly how many sums do we need to compute for an array of size n? ? We propose the following algorithm to compute some of the entries of a 2D array S: int main(void) { vector cdouble> R; // initialize R to contain n daily step counts vector > S; for (int b = 0; b temp; for (int a = 0; a