Python - 添加到列表多次拼接，優化，算法

Question

我想添加一個常量num_to_add給列表I中的每個列表元素，在一個拼接l [i：j（including）]中我給了很多表單的查詢[i，j，num_to_add]。

其中t的格式爲[[i，j，num_to_add]，[i，j，num_to_add]等] 我將t的每個元素添加到完全由零構成的列表I中。

我當前的代碼是這樣的： 我循環遍歷t中的子列表，我的查詢，並將num_to_add添加到每個列表拼接元素。我輸出列表I中小於整數n的元素數量。

我怎樣才能從嵌套for循環優化這個？這是針對可能適用於其他項目的一小部分問題。

EDIT 4： 樣品輸入：

4 
1 
3 
1 3 1 
2 3 2 
3 3 2 

EDIT 5： 全碼：

I = [0] * int(input()) 
n = int(input()) 
j = int(input()) 
t = [list(map(int, input().split())) for i in range(j)] 

tree = [] 
for i in range(1, 2*len(I)+1): 
    tree.append([0,0]) 

def update(pos , left , right , i , j , val): 

    ####updating segment tree to add value val in list l from index i to j 

    i=max(i , left) 
    j=min(j , right) 
    if i > j: 
     return 

    if i==left and j==right: 
     tree[pos][0] = tree[pos][0] + val*(j - i + 1) 
     tree[pos][1] = tree[pos][1] + val 
     return 

    mid = (left + right)/2 

    ### the range breaks down into two parts left to mid and mid+1 to right 
    ### at positions 2*pos and 2*pos+1 in tree respectively 

    update(2*pos , left , mid , i , j , val) 
    update(2*pos + 1 , mid+1 , right , i , j , val) 
    tree[pos][0] = tree[2*pos][0] + tree[2*pos + 1][0] + tree[pos][1]*(right - left +1) 


def getvalue(pos , left , right , i , j): 

    ###gets sum of elements in list from index i to j in our case 
    ### i will be equal to j , will see below 

    i = max(i , left) 
    j= min(j , right) 
    if i > j: 
     return 0 
    if i==left and j==right: 
     return tree[pos][0] 

    mid = (left + right)/2 
    return getvalue(2*pos , left , mid , i , j) + getvalue(2*pos+1 , mid+1 , right , i , j) + tree[pos][1]*(j - i + 1) 

###Remember l is 1 based indexed 
for i in range(len(t)): 
    update(1 , 1 , len(I) , t[i][0] , t[i][1] , t[i][2]) 

ans = 0 

###Remember l is 1 based indexed 
for i in range(1 , len(I)+1): 
    ###see we only use getvalue where i and j parameters of getvalue are same 
    value = getvalue(1 , 1 , len(I) , i , i) 
    if value < n: 
     ans = ans + 1 

print(ans) 

錯誤：

Traceback (most recent call last): 
    File, line 58, in <module> 
    value = getvalue(1 , 1 , len(I) , i , i) 
# A lot of these: 
    File "/home/max3/Documents/Python/DMOJ TCE Battle Positions.py", line 47, in getvalue 
    return getvalue(2*pos , left , mid , i , j) + getvalue(2*pos+1 , mid+1 , right , i , j) + tree[pos][1]*(j - i + 1) 
# And one of this. 
    File "/home/max3/Documents/Python/DMOJ TCE Battle Positions.py", line 44, in getvalue 
    return tree[pos][0] 
IndexError: list index out of range 

Answer 1

甲段TR ee爲您提供更新和檢索列表中元素總和的能力O（logN）其中N是列表大小。查找並說服自己如何使用細分樹 Segment Tree。
讓樹（另一個列表）是段樹，它是你的清單升也是它的每一個元素是大小兩個另一個列表，初始化爲零的兩倍。（我同時服用升和樹是基於1的索引）。那是所有我從1到2N 樹[I] = [0,0]。 樹[i] [0]是此索引對應的範圍和tree [i] [1]在更新時添加到此範圍的值。例如樹[1] [0]存儲範圍1至N中的元素總和。

I = [0] * int(input()) 
n = int(input()) 
j = int(input()) 
t=[] 
tree=[] 
for i in range(j): 
    s=raw_input() 
    l=s.split() 
    for x in range(len(l)): 
     l[x]=int(l[x]) 
    t.append(l) 

for i in range(1,2*len(I)+1): 
    tree.append([0,0]) 

def update(pos , left , right , i , j , val): 

    ####updating segment tree to add value val in list l from index i to j 

    i=max(i , left) 
    j=min(j , right) 
    if i > j: 
     return 

    if i==left and j==right: 
     tree[pos][0] = tree[pos][0] + val*(j - i + 1) 
     tree[pos][1] = tree[pos][1] + val 
     return 

    mid = (left + right)/2 

    ### the range breaks down into two parts left to mid and mid+1 to right 
    ### at positions 2*pos and 2*pos+1 in tree respectively 

    update(2*pos , left , mid , i , j , val) 
    update(2*pos + 1 , mid+1 , right , i , j , val) 
    tree[pos][0] = tree[2*pos][0] + tree[2*pos + 1][0] + tree[pos][1]*(right - left +1) 


def getvalue(pos , left , right , i , j): 

    ###gets sum of elements in list from index i to j in our case 
    ### i will be equal to j , will see below 

    i = max(i , left) 
    j= min(j , right) 
    if i > j: 
     return 0 
    if i==left and j==right: 
     return tree[pos][0] 

    mid = (left + right)/2 
    return getvalue(2*pos , left , mid , i , j) + getvalue(2*pos+1 , mid+1 , right , i , j) + tree[pos][1]*(j - i + 1) 

現在你的段樹已準備就緒，我們處理查詢，我們只是計數低於某個值ň 元素的數量。

for i in range(len(t)): 
    update(1 , 1 , N , t[i][0] , t[i][1] , t[i][2]) 

ans = 0 

###Remember l is 1 based indexed 
for i in range(1 , N+1): 
    ###see we only use getvalue where i and j parameters of getvalue are same 
    value = getvalue(1 , 1 , N , i , i) 
    if value < n: 
     ans = ans + 1 

print ans 

的過所有這些算法的複雜度是Ò相比你 這在最壞的情況下會是ø（（t）的* logN個+ N的大小）（的大小（T）* N）。此外，由於查詢範圍更新我 已延遲更新（谷歌懶惰傳播），以便更新和查詢一次保留在 O（logN）。PS：原諒我的壞python。