c - Is there any faster implementation for this Splay Tree range sum? -

-

i have coded splay tree. nodes represented this.

struct node{     node *l;  /// left  node     node *r;  /// right node     int v;    /// value };

now, need know summation of numbers in tree within range. this, implemented following function named summation.

void summation(node *r, int st, int ed) {     if(!r) return;     if(r->v < st){        /// should not call left side         summation(r->r, st, ed);     }     else if(r->v > ed){   /// should not call right side         summation(r->l, st, ed);     }     else{                /// should call both side         ret+=r->v;         summation(r->l, st, ed);         summation(r->r, st, ed);     }     return; }

ret global int variable initialized 0 before calling summation function. 2 parameters st & ed defines range (inclusive).

the summation function works @ complexity of o(n). can suggest faster implementation this??

this splay tree implementation did time ago , tested against spoj evaluation system (written in c++) :

https://ideone.com/aqgepf

this tree implementation supports u asking (range sum in o(log(n)).

the key idea here use split , merge, extract subtree covering range. additionally each node contains field sum, sum of keys in subtree. sum field lazily evaluated , relayed during split operation (along splitting line), allows not go deeper levels not required calculated.


Comments

Post a Comment

Popular posts from this blog

Spring Boot + JPA + Hibernate: Unable to locate persister -

-
i trying work entity inside request method of spring boot application. entity in project , pom.xml has dependencies it. why error message?: org.hibernate.unknownentitytypeexception: unable locate persister: com.ric.bill.model.bs.par package com.ric.web; import java.util.concurrent.atomic.atomiclong; import javax.persistence.entitymanager; import javax.persistence.persistencecontext; import net.sf.ehcache.cachemanager; import net.sf.ehcache.management.cache; import net.sf.ehcache.management.cachestatistics; import org.hibernate.stat.statistics; import org.springframework.beans.factory.annotation.autowired; import org.springframework.boot.autoconfigure.domain.entityscan; import org.springframework.cache.annotation.enablecaching; import org.springframework.transaction.annotation.enabletransactionmanagement; import org.springframework.transaction.annotation.propagation; import org.springframework.transaction.annotation.transactional; import org.springframework.web.bind.annotati...
Read more

go - Golang: panic: runtime error: invalid memory address or nil pointer dereference using bufio.Scanner -

-
i implementing go program uses bufio.scanner , bufio.writer have packaged code follows package main import ( "fmt" "player/command" "strings" ) func main() { //enter code here. read input stdin. print output stdout commands.scanner.scan() { //scan new line , send comand variable check command exist or not input := strings.split(strings.trim(commands.scanner.text(), " "), " ") command := input[0] if command == "" { fmt.printf("$ %s:", commands.pwd) continue } if !commands.commands[command] { commands.throwerror("cannot recognize input.") } else { commands.execute(command, input[1:], nil) } fmt.printf("$ %s:", commands.pwd) } } i using init.go file in main package follows package main import ( "flag" "player/sourc...
Read more

c - double free or corruption (fasttop) -

-
this code reads null terminated string file (file containing null terminated strings & should provide index wanted string). error: *** error in `./main': double free or corruption (fasttop): 0x090a4a80 *** aborted code: char *tmp_realloc=null; char *sstring=null; int i=1; /*set file pointer point string*/ fseek(fh,index,seek_set); sstring=(char*)malloc(sizeof(char)); if(sstring == null) return null; tmp_realloc=sstring; while( (*(sstring+i-1)=(char)fgetc((file*)fh)) != 0x0 ) { /*reallocate more memory*/ tmp_realloc=(char*)realloc((char*)sstring,++i); /*if not same address copy old new & set old point new*/ if(tmp_realloc != sstring){ strcpy((char*)tmp_realloc,(char*)sstring); free(sstring); sstring=tmp_realloc; } } could tell me pointer causing issue (& reason) ? remove part /*if not same address copy old new & set old point new*/ if(tmp_realloc != sstring){ strc...
Read more