algorithm - worst case running time of segment tree -

-

how range sum in segment tree o(logn) worst case?? shouldn't o(n)? if during range sum operation,we traverse down both left , right nodes per algorithm?

lets call active node node stores interval neither included in interval nor covered interval. easy spot there @ 2 active nodes on each level traverse. if node not active not need recurse in - if interval covered add value written in node, if interval not intersect 1 interested in skip it. number of operations algorithm perform in order of levels of tree or o(log(n)).


Comments

Post a Comment

Popular posts from this blog

c - CUDA code not processing if block properly -

-
stuck @ if block right below //step 5, issue code not progress or after given if block. need figure out how particular issue settled before starting task of generating parallel code. if run code see 1 print statement indicates value of "one" , 2 "i" , "j". after if block begins, none of other print statements hit. result quite stuck, aware specific issue, however, cannot seem determine it's cause. any appreciated! in advance! input file sample. >386.fasta.screen.contig1 gagtttgatcctggctcagaatcaacgctggcggcgcgcttaacacatgc aagtcgaacgagaaagtggagcaatccatgagtacagtggcgtacgggtg agtaacacgtgggtaatctacctcttagtggggaataactttgggaaacc gaagctaataccgcataagctcgagagaggaaagcagcaatgcgctgaga gaggagcccgcggccgattagctagttggcagggtaaaagcctaccaagg cagagatcggtagccggcctgagagggcacacggccacactggcactgaa acacgggccagactcctacgggaggcagcagtggggaatcttgcacaatg ggggcaaccctgatgcagcgacgccgcgtgagcgatgaagcccttcgggg tgtaaagctctttcgtcagggaagatagtgacggtacctggagaagcagc tgcggctaactacgt...
Read more

oracle11g - get root domain from url Oracle sql regex_substr -

-
i have query root domain urls below : select regexp_substr(regexp_replace('https://creditcards.chase.com/credit-cards/bp-credit-card.aspx', '^http[s]?://(www\.)?|^www\.', '', 1), '(\.\w+)+') domain dual; which returns out put : '.chase.com' how can ignore first dot in outoput regex in above query? note : need root domain, i.e, 'chase.com' thanks. select regexp_substr('https://creditcards.token.chase.com/credit-cards/bp-credit-card.aspx', '(^http[s]?://(www\.)?|^www\.)(\w+\.)*(\w+\.\w+)', 1, 1, 'i', 4) domain dual;
Read more

xcode - Swift Playground - Files are not readable -

-
Image
files not readable in swift playground . how make files readable? same code runs on xcode terminal app, fails on swift playground. demo code below. import foundation println("hello, world!") var fname:string = "/users/holyfield/desktop/com.apple.iconcomposer.plist" var fm:nsfilemanager = nsfilemanager.defaultmanager() if(fm.fileexistsatpath(fname)){ println("file exists") if(fm.isreadablefileatpath(fname)){ println("file readable") var fd:nsdata? = nsdata(contentsoffile: fname) println(fd?.length) let pl = nsdictionary(contentsoffile: fname) println(pl?.count) println(pl?.allkeys) }else{ println("file not readable") } } else{ println("file not exists") } sample images: i have thank nate cook first quick response , solid answer. just case share answer post, title misleading. see nate's answer here: https://stackoverf...
Read more