CSES - Range Sum Queries In Python

help
1

Problem:
Given an array of n integers, your task is to process q queries of the form: what is the sum of values in range [a,b]?

Input

The first input line has two integers n and q . The number of values and queries.

The second line has n integers x1,x2,…xn: the array values.

Finally, there are q lines describing the queries. Each line has two integers aa and bb: what is the sum of values in range [a,b]?

Output

Print the result of each query.

Example

Input:
8 4
3 2 4 5 1 1 5 3

2 4
5 6
1 8
3 3

Output:
11
2
24
4

My solution
m, n = map(int,input().split())
arr = list(map(int,input().split()))
for i in range(n):
a,b = map(int,input().split())
sum_a_b = arr[a-1:b]
print (sum(sum_a_b))

Getting TLE in second task .
what i do to get AC in python.

2

Range Sum Queries can be easily solved using Prefix Sum, provided there are no updates.
In case there are update queries too, you would use Segment Trees.
Using Prefix Sum, the code would be:

n, q = map(int,input().split())
l = list(map(int,input().split()))
prefix = [0]
for i in range(n):
    prefix.append(prefix[-1] + l[i])
for i in range(q):
    a, b = map(int,input().split())
    print(prefix[b]-prefix[a-1])
2 Likes
3

see what u did is , just sum from l to r each time which gives u TLE , instead of this u can use prefix sum , segment tree , BIT , SQRT decomposition [ this is basic question for all of these algorithm , don’t fear by their name]

1 Like
4

pp
pp694×616 58.4 KB

while using prefix Sum . Getting TLE

5

So what i do?

6

give me que. link

7

https://cses.fi/problemset/task/1646

8 
n,q = map(int,input().split(' '))
ls = list(map(int,input().split(' ')))
pre = [0]*n
pre[0] = ls[0]
for i in range(1,n):
    pre[i] = pre[i-1]+ls[i]
 
for _ in range(q):
    a,b = map(int,input().split(' '))
    a-=1
    b-=1
    if(a==0):
        print(pre[b])
    else:
        print(pre[b]-pre[a-1])

get TLE in cpython3 , but AC in pypy

in c++ using Binary Index Tree (aka Fenwick Tree / BIT ) : “https://cses.fi/paste/c7245c3afad5f4c7f303e/”

1 Like
9

This issue could be resolved using FAST IO, I guess.
Let me provide you AC solution in Python.
Screenshot from 2020-11-20 11-36-39

"""
 _____   _    _   __    __     ____     __    _
/ ____| | |  | | |  \  /  |   /    \   |  \  | |
| |___  | |  | | |   \/   |  /   _  \  | . \ | |
\____ \ | |  | | | |\__/| | |   /_\  | | |\ \| |
____| | | \__/ | | |    | | |   __   | | | \ ` |
|_____/ \______/ |_|    |_| |__|  |__| |_|  \__|

"""
"""
/*
Template by Sai Suman Chitturi
Linkedin: https://www.linkedin.com/in/sai-suman-chitturi-9727a2196/
Hackerrank: https://www.hackerrank.com/skynetasspyder?hr_r=1
Codechef: https://www.codechef.com/users/suman_18733097
Codeforces: http://codeforces.com/profile/saisumanchitturi
Github: https://github.com/ChitturiSaiSuman
Hackerearth: https://www.hackerearth.com/@chitturi7
SPOJ: Sai Suman Chitturi @out_of_bound
*/
"""
from sys import stdin,stdout,stderr,setrecursionlimit
from math import pi,sqrt,gcd,ceil,floor,log2,log10,factorial
from math import cos,acos,tan,atan,atan2,sin,asin,radians,degrees,hypot
from bisect import insort,insort_left,insort_right,bisect_left,bisect_right,bisect
from functools import reduce
from itertools import combinations,combinations_with_replacement,permutations
from fractions import Fraction
from random import choice,getrandbits,randint,random,randrange,shuffle
from re import compile,findall,escape,search,match
from statistics import mean,median,mode
from heapq import heapify,heappop,heappush,heappushpop,heapreplace,merge,nlargest,nsmallest
from collections import deque,OrderedDict,defaultdict
from collections import Counter,namedtuple,ChainMap,UserDict,UserList,UserString
# from numpy import dot,trace,argmax,argmin,array,cumprod,cumsum,matmul

mod = 10**9+7
lcm = lambda x,y: ((x*y)//gcd(x,y))
add = lambda x,y: (x%mod+y%mod)%mod
sub = lambda x,y: ((x%mod-y%mod)+mod)%mod
mul = lambda x,y: ((x%mod)*(y%mod))%mod
inverse = lambda x: (pow(x,mod-2,mod))
setBitCount = lambda x: bin(x).count("1")
sumOfDigits = lambda x: sum([int(i) for i in str(x)])

setrecursionlimit(10**6)

size = 10**6+1

def preCompute():
    return

def solve():
    return

def main():
    io = IO()
    testcases = 1
    if testcases == 0:
        testcases = io.nextInt()
    preCompute()

    for test in range(testcases):
        # io.write("Case #%d: "%(test+1),end="")
        n, q = io.Tuple()
        l = io.List()
        prefix = [0]
        for i in range(n):
            prefix.append(prefix[-1]+l[i])
        for i in range(q):
            a,b = io.Tuple()
            io.write(prefix[b] - prefix[a-1])

class IO:
    def next(self):
        return stdin.readline().strip()
    def nextLine(self):
        return self.next()
    def String(self):
        return self.next()
    def nextStrings(self):
        return list(map(str,self.next().split()))
    def nextInt(self):
        return int(self.next())
    def Int(self):
        return self.nextInt()
    def nextFloat(self):
        return float(next())
    def Float(self):
        return self.nextFloat()
    def nextList(self):
        return list(map(int,self.next().split()))
    def List(self):
        return self.nextList()
    def nextTuple(self):
        return tuple(map(int,self.next().split()))
    def Tuple(self):
        return self.nextTuple()
    def debug(self,*obj,sep=" ",end="\n"):
        string = sep.join([str(item) for item in obj])+end
        stderr.write(string)
    def print(self,*obj,sep=" ",end='\n'):
        string = sep.join([str(item) for item in obj])+end
        stdout.write(string)
    def write(self,*obj,sep=" ",end="\n"):
        self.print(*obj,sep=sep,end=end)

main()
1 Like
10

Thanks Bro :slight_smile:.

1 Like
11

Thank You Bro :slight_smile:.

1 Like