Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays.
A subarray is a contiguous subsequence of the array.
Return the sum of all odd-length subarrays of arr.
 
Example 1:
Input: arr = [1,4,2,5,3]
Output: 58
Explanation: The odd-length subarrays of arr and their sums are:
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58
Example 2:
Input: arr = [1,2]
Output: 3
Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.
Example 3:
Input: arr = [10,11,12]
Output: 66

 
Constraints:

1 <= arr.length <= 100
1 <= arr[i] <= 1000

Source: leetcode | Difficulty: EASY
Tags: Mathematics

Data structures

Range queries

Starter code: class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        

Solutions:
class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		total = 0
		for i in range(len(arr)):
			totalisubarrays = (len(arr) - i) * (i + 1)
			if totalisubarrays % 2 == 1:
				totalisubarrays += 1
			oddisubarrays = totalisubarrays // 2
			total += arr[i] * oddisubarrays
		return total


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		ans = 0
		n = len(arr)
		for (i, j) in enumerate(arr):
			ans += ((i + 1) * (n - i) + 1) // 2 * j
		return ans


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		total = 0
		length = 1
		while length <= len(arr):
			for i in range(len(arr) - length + 1):
				total += sum(arr[i:i + length])
			length += 2
		return total


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		l = len(arr)
		s = 0
		for i in range(l):
			for j in range(i + 1, l + 1, 2):
				subarr = arr[i:j]
				s += sum(subarr)
		return s


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		total = 0
		size = len(arr)
		for n in range(1, size + 1, 2):
			for i in range(size - (n - 1)):
				total += sum(arr[i:i + n])
		return total


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		li = []
		sumv = 0
		n = len(arr)
		for i in range(1, n + 1, 2):
			li.append(i)
		for i in li:
			for j in range(len(arr)):
				if i + j <= n:
					sumv += sum(arr[j:j + i])
				else:
					break
		return sumv


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		l = len(arr)
		sumtotal = 0
		for i in range(1, l + 1, 2):
			for j in range(1, l + 1):
				if j + i - 1 < l + 1:
					sumtotal += sum(arr[j - 1:j + i - 1])
		return sumtotal


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		res = 0
		n = len(arr)
		for k in range(1, n + 1, 2):
			for (i, v) in enumerate(arr):
				res += v * min(n - k + 1, k, i + 1, n - i)
		return res


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		total_sum = 0
		sum_arr = [[0] * (len(arr) + 1) for i in range(len(arr))]
		for i in range(len(arr)):
			for j in range(len(arr) - i):
				start = j
				end = j + i + 1
				sub_sum = 0
				if end - start == 1:
					sum_arr[start][end] = arr[start]
					sub_sum = arr[start]
				else:
					sub_sum = arr[start] + sum_arr[start + 1][end]
					sum_arr[start][end] = sub_sum
				if (end - start) % 2 == 1:
					total_sum += sub_sum
		return total_sum


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		if arr == []:
			return 0
		sum_ = 0
		for i in range(len(arr)):
			for j in range(i + 1, len(arr) + 1):
				val = arr[i:j]
				if len(val) % 2 != 0:
					sum_ += sum(val)
		return sum_


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		total_sum = 0
		for i in range(len(arr)):
			for j in range(len(arr) - i):
				start = j
				end = j + i + 1
				sub_arr = arr[start:end]
				if (end - start) % 2 == 1:
					total_sum += sum(sub_arr)
		return total_sum


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		result = 0
		for i in range(1, len(arr) + 1, 2):
			for j in range(0, len(arr) + 1 - i):
				print(j, j + i)
				result += sum(arr[j:j + i])
		return result


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		ret = 0
		for i in range(len(arr)):
			ret += arr[i] * ceil((len(arr) - i) * (i + 1) / 2)
		return ret


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		xdict = {}
		print(arr[0:1])
		for i in range(0, len(arr)):
			sumx = 0
			for j in range(0, len(arr) - i):
				sumx = sumx + sum(arr[j:j + i + 1])
			xdict[i] = sumx
		print(xdict)
		sumx = 0
		for i in xdict:
			if i % 2 == 0:
				sumx = sumx + xdict[i]
		return sumx


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		total = 0
		for i in range(len(arr)):
			for j in range(len(arr)):
				a = arr[i:j + 1]
				if not len(a) % 2 == 0:
					total += sum(a)
		return total


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		m = len(arr)
		s = 0
		a = []
		for i in range(m):
			t = 0
			while t <= m:
				a = arr[i:t]
				t += 1
				if len(a) % 2 != 0:
					s = s + sum(a)
		return s


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		arrayLength = len(arr) + 1
		oddLengthSum = 0
		if arrayLength <= 2:
			return sum(arr)
		for subArrayLength in range(arrayLength)[1::2]:
			for i in range(arrayLength - subArrayLength):
				for value in arr[i:i + subArrayLength]:
					oddLengthSum += value
		return oddLengthSum


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		ans = 0
		i = 0
		j = 1
		while True:
			if i > len(arr) - 1:
				break
			if len(arr[i:j]) % 2 != 0:
				ans = ans + sum(arr[i:j])
			j += 1
			if j > len(arr):
				i += 1
				j = i + 1
		return ans


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		flag = True
		i = 1
		subSum = 0
		totalSum = 0
		while flag:
			subFlag = True
			start = 0
			end = i
			while subFlag:
				for j in arr[start:end]:
					subSum += j
				if end == len(arr):
					totalSum += subSum
					print((subSum, totalSum))
					subSum = 0
					subFlag = False
				else:
					start += 1
					end += 1
			if i == len(arr) or i == len(arr) - 1:
				flag = False
			else:
				i += 2
		return totalSum


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		s = 0
		s += sum(arr)
		for j in range(3, len(arr) + 1, 2):
			for i in range(0, len(arr)):
				if len(arr[i:i + j]) % 2 != 0 and len(arr[i:i + j]) != 1 and (i + j <= len(arr)):
					s += sum(arr[i:i + j])
		return s


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		ret = 0
		subArrs = []
		starting = 0
		ending = len(arr)
		for i in range(len(arr)):
			while ending >= starting:
				if (ending - starting) % 2 != 0:
					subArrs += [arr[starting:ending]]
					ending -= 2
				else:
					ending -= 1
			starting += 1
			ending = len(arr)
		for i in subArrs:
			for j in i:
				ret += j
		return ret


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		(res, n) = (0, len(arr))
		for (i, a) in enumerate(arr):
			res += ((i + 1) * (n - i) + 1) // 2 * a
		return res


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		return self.backtrack(arr, 0, 0, 0)

	def backtrack(self, arr, i, end, s):
		if end == len(arr):
			return s
		elif i > end:
			return self.backtrack(arr, 0, end + 1, s)
		elif len(arr[i:end + 1]) % 2 != 0:
			s += sum(arr[i:end + 1])
			return self.backtrack(arr, i + 1, end, s)
		else:
			return self.backtrack(arr, i + 1, end, s)


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		res = sum(arr)
		for i in range(0, len(arr)):
			count = 2
			while i + count < len(arr):
				for j in range(i, count + i + 1):
					res += arr[j]
				count += 2
		return res


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		total = 0
		for length in range(1, len(arr) + 1):
			if length % 2 == 0:
				continue
			for (i_start, start) in enumerate(arr):
				if i_start + length - 1 < len(arr):
					for i in range(i_start, i_start + length):
						total += arr[i]
				else:
					break
		return total


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		ans = 0
		for i in range(1, len(arr) + 1, 2):
			for j in range(len(arr) + 1 - i):
				for k in range(i):
					ans += arr[j + k]
		return ans


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return arr[0]
		result = 0
		l = r = 0

		def getSum(array, start, end):
			local_sum = 0
			for i in range(start, end):
				local_sum += array[i]
			return local_sum
		while l < len(arr) - 1:
			if r > len(arr) - 1:
				l += 1
				r = l
			result += getSum(arr, l, r + 1)
			r += 2
		return result


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		(cur_sum, prefix_sum) = (0, [0] * (len(arr) + 1))
		ret = 0
		for i in range(1, len(arr) + 1):
			cur_sum += arr[i - 1]
			prefix_sum[i] = cur_sum
			for j in range(1, i + 1, 2):
				ret += prefix_sum[i] - prefix_sum[i - j]
		return ret


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		n = len(arr)
		s = 0
		for i in range(n):
			for j in range(1, n + 1, 2):
				if i + j - 1 < n:
					for x in range(j):
						s += arr[x + i]
		return s


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		ans = 0
		N = len(arr)
		sumv = (N + 1) * [0]
		for i in range(N):
			sumv[i + 1] = sumv[i] + arr[i]
		ans = 0
		for i in range(1, N + 1):
			ans += sumv[i] * ((i + 1) // 2 - (N - i + 1) // 2)
		return ans


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		total = 0
		subArrLen = 1
		while subArrLen <= len(arr):
			i = 0
			j = subArrLen
			subTotal = sum(arr[:j])
			total += subTotal
			while j < len(arr):
				subTotal -= arr[i]
				subTotal += arr[j]
				total += subTotal
				i += 1
				j += 1
			subArrLen += 2
		return total


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		(n, sum_odd) = (len(arr), 0)
		p_sum = [0] * (n + 1)
		for (i, a) in enumerate(arr):
			p_sum[i + 1] = p_sum[i] + a
		for (i, p) in enumerate(p_sum):
			for j in range(i + 1, n + 1, 2):
				sum_odd += p_sum[j] - p_sum[i]
		return sum_odd


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		n = len(arr)
		prefix = [0] * (n + 1)
		for i in range(n):
			prefix[i] = prefix[i - 1] + arr[i]
		ans = 0
		for s in range(1, n + 1, 2):
			for i in range(n):
				if i + s > n:
					break
				ans += prefix[i + s - 1] - prefix[i - 1]
		return ans


class Solution:

	def sumOddLengthSubarrays(self, arr: List[int]) -> int:
		total = 0
		for i in range(len(arr)):
			temp = 0
			for j in range(i, len(arr)):
				temp += arr[j]
				if (j - i) % 2 == 0:
					total += temp
		return total