For a given array of integers, we have to calculate XORed sum withing a given range [L, R], by XORed sum I mean Σ(Arr[i]^p) where i:[L,R] and p is some number. This can be easily done while calculating the XORed sum till every i-th element in array from beginning of the array. Now the problem occures when the p changes very frequently. And recalculating XORed sum till every i-th element does not seems to be an ideal solution in this case. I guess this can be done using fenwick tree or BIT. But I am not able to figure out how to proceed with fenwick tree or BIT. Any help would be appreciated.
range XORed sum using BIT or Fenwick tree
753 views Asked by Roshan At
1
There are 1 answers
Related Questions in ALGORITHM
- MCNP 6 - Doubts about cells
- Given partially sorted array of type x<y => first apperance of x comes before first of y, sort in average O(n)
- What is the algorithm behind math.gcd and why it is faster Euclidean algorithm?
- Purpose of last 2 while loops in the merge algorithm of merge sort sorting technique
- Dots and Boxes with apha-beta pruning
- What is the average and worst-case time complexity of my string searching algorithm?
- Building a School Schedule Generator
- TC problem 5-2:how to calculate the probability of the indicator random variable?
- LCA of a binary tree implemented in Python
- Identify the checksum algorithm
- Algorithm for finding a subset of nodes in a weighted connected graph such that the distance between any pair nodes are under a postive number?
- Creating an efficent and time-saving algorithm to find difference between greater than and lesser than combination
- Algorithm to find neighbours of point by distance with no repeats
- Asking code suggestions about data structure and algorithm
- Heap sort with multithreading
Related Questions in XOR
- Negate every bit value of a binary in C
- XOR Hex and ASCII
- XOR Encryption in C with key
- Operating XOR over a defined set of iterating matrices in python
- How to model an exclusive or in OWL?
- XOR with NEAT Algorithm
- XORing all values of a (2d) numpy array together
- XOR operator problems in C
- XOR command fails
- Is it possible to reverse the XOR of multiple variables?
- Can we replace XOR with multiply-add?
- Correctly embedding and extracting Unicode data from an image
- Execution Time Difference between two bit-wise differential execution
- How to Improve XORing of large uint64 arrays?
- Backpropagation in Neural Network for XOR data
Related Questions in FENWICK-TREE
- Why range update in Fenwick Tree is meant to has no impact on nodes others than these in range?
- Simpler Alternatives to Fenwick Trees
- Why we need two fenwick tree to get range sum of [l, r] given there are array of numbers and range updates and queries are performed on the array?
- How to make this fenwick tree LIS solution faster?
- Can Fenwick Tree and Segment Tree in C++ perform insertions and deletions in logarithmic time?
- Optimise array calculation in python
- Why would you ever add 10^9+7 to a number and then take mod with 10^9+7
- Dynamic Range Sum Queries
- Insertion and Deletion on segment tree or BIT tree?
- Calculating sub array sums with a Fenwick tree
- Find the number of players cannot win the game?
- What does `(i & (i + 1)) - 1` mean? (in Fenwick Trees)
- Fenwick tree vs Segment tree
- Point Updates in Fenwick Tree
- Get index of element in set (STL C++) in asysmtotically less than O(n)
Related Questions in BINARY-INDEXED-TREE
- How to Use Binary Indexed Tree for Counting Reverse Pairs in an Array?
- Why we need two fenwick tree to get range sum of [l, r] given there are array of numbers and range updates and queries are performed on the array?
- Quick Way of Finding How many Substrings has first and last character repeated inside
- Binary Indexed Tree: Why does "i + lowBit(i)" work?
- Fenwick tree(BIT). Find the smallest index with given cumulative frequency in O(logN)
- how to increase the size limit of a mutable list in kotlin?
- How can we calculate weighted cumulative sum of squares with prefix range updates by one?
- What does "x += x & (-x)" mean?
- C++ Counting inversions in array, Fatal Signal 11 (BIT)
- Update step in Fenwick Trees
- Count "minimal" values
- Difference between Binary Search Tree and Binary Index Tree
- Answer queries about the number of distinct numbers in a given range
- how to get inversion count with update
- can someone provide me the algorithm of 2-d binary indexed tree?
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
Popular Tags
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
We can solve the problem for each bit independently.
Let's assume that we want to compute the contribution of the
k-th bit to the answer. If it's set inp, the answer is the number of elements in the range with the value of this bit equal to zero (otherwise, it's the same thing but for the elements with this bit equal to one).How to count the number of such elements efficiently? We can build a prefix sums array for each bit. This way, we obtain the number of elements with or without the given bit in a range in constant time.