Efficient transitive operations using binary indexed trees

In this paper, we propose a novel data structure and the algorithms to build, update and perform range query operations of transitive function. The update and query operation takes O( log ( n )) time, and the space required for operating data is also O( cn ), where c=3 proving it to be efficient tha...

Full description

Saved in:
Bibliographic Details
Published in:International journal of information technology (Singapore. Online) 2021-06, Vol.13 (3), p.1155-1163
Main Authors: Tewari, Kartikey, Shrivastava, Abhijeet, Yadav, Arun Kumar, Yadav, Divakar
Format: Article
Language:English
Subjects:
Artificial Intelligence
Computer Imaging
Computer Science
Image Processing and Computer Vision
Machine Learning
Original Research
Pattern Recognition and Graphics
Software Engineering
Vision
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we propose a novel data structure and the algorithms to build, update and perform range query operations of transitive function. The update and query operation takes O( log ( n )) time, and the space required for operating data is also O( cn ), where c=3 proving it to be efficient than other data structures such as segment tree and sparse table. Experimental analysis shows the statistical evidence of proposed algorithm and conclude that it provides a good trade-off between space and time complexity in comparison to existent methods.
ISSN:2511-2104
2511-2112
DOI:10.1007/s41870-021-00685-z