algorithm - Cumulative frequency table with creation in linear or better than linear complexity? -

i trying solve algorithmic problem, , solve within time constrains need implement cumulative frequency table creation takes linear or better linear time? inputs integers only; hence, keys of frequency table integers only. simple implementation came follows (assume cumulative_freq_table hashmap in following code.):

read x key in range(x, n):  if key in cumulative_freq_table:   cumulative_freq_table[key] += 1      

i haven't studied algorithms related course, guess complexity around o(n^2). can done in time better o(n^2)?

off-line approach

if happy use 2 passes can this:

for each x:   read x   freq_table[x] += 1  t = 0 key in range(0,n):   t += freq_table[key]   cumulative_freq_table[key] = t  

this linear.

on-line approach

the problem linear approach requires data seen before can access cumulative frequency table.

there alternative approaches allow continual access cumulative frequency, have higher complexity.

for example, have @ fenwick trees approach uses o(log(n)) operations each element.