A simple approach to segment trees

sahildua2305:

A simple approach to Segment Trees!

Originally posted on Everything Under The Sun:

A segment tree is a tree data structure that allows aggregation queries and updates over array intervals in logarithmic time. As I see it, there are three major use cases for segment trees:

  1. Static or persistent segment trees: This is probably the most common use case. We preprocess an array of N elements to construct a segment tree in O(N). Now, we can query aggregates over any arbitrary range/segment of the array in O(log N).
  2. Segment tree with point updates: This allows us to update array values, one at a time in O(log N), while still maintaining the segment tree structure. Queries over any arbitrary range still occurs in O(log N).
  3. Segment tree with range updates: This allows us to update a range of array elements at once in O(N) in the worst case, however problem specific optimizations and lazy propagation typically give huge improvements. Queries over any arbitrary range still occurs in O(log N).

In this post, I’ll…

View original 1,234 more words

Important Topics for Competitive Programming.

Originally posted on vishalpanwar:

You may have wondered about the vast and endless nature of topics important(or I should say sufficient) for competitive programming point of view. Well to sum it all I have prepared a list(huge one!!!). It contains all the famous problems,algorithms and data structure…………………………

(a)Number Theory

  1. Prime Number Generation  (Sieve, Segmented Sieve)
  2. Euler Totient Theorem
  3. Fermat’s Theorem
  4. HCF & LCM (Euclid)
  5. Linear Diophantine Equations (Extended Euclid)
  6. Modulus Arithmetic (addition,multiplication,subtraction,modular Inverse)
  7. Cycle Finding (Floyd Algo and Brent Algo)
  8. Integer Factorization (Trial Division , Pollard Rho method)
  9. Lucas Theorem  (Simple & Advance)
  10. Chinese Remainder Theorem
  11. Wilson Theorem
  12. Miller – Rabin Primality Testing
  13. Perfect Numbers
  14. Goldbach Conjecture

(b)Probability

  1. Basic Probability and Conditional Probability
  2. Random Variables
  3. Probability Generating Functions
  4. Expectation
  5. Probability Distribution [Binomial, Poisson, Normal,Bernoulli]

(c)Counting

  1. Pigeonhole principle
  2. Inclusion Exclusion
  3. Special Numbers  [Stirling,Fibonacci,Catalan, Eulerian, Harmonic, Bernoulli]
  4. Polya Counting
  5. Burnside lemma

(d)Permutation Cycles

(e)Linear Algebra

  1. Addition And Subtraction Of Matrices
  2. Multiplication ( Strassen’s algorithm ), Logarithmic…

View original 433 more words

Suffix Arrays – A simple Tutorial

sahildua2305:

An Awesome Post on Suffix Arrays !

Originally posted on Outlooking life:

Suffix Arrays

It is the data structure to look out for when you are going for string Searching and want to reduce the time complexity greatly.  So, Let us examine and start from basics.

What are Suffix Arrays ?

As simple as it can get , suffix arrays represent the rank of all possible suffixes of a given string .For example ,

String  S = “ABDCASD”

Then the suffixes for the string S (with the numbers in front represent are ,

7 $ *

6 D

5 SD

4 ASD
3 CASD

2 DCASD

1 BDCASD

0 ABDCASD

*$, A null character can be called a suffix of every string as it does no addition to the string itself . We will later on see why we chose to add NULL character to our algorithm . For NULL character that we used, we assume have highest lexicographic priority .

Now,

View original 746 more words

Featured Image -- 192

‘WhatsApp For the Workplace’ Cotap Adds Universal Chat Feature Accessible Via URLs

Originally posted on TechCrunch:

Cotap, the enterprise messaging app founded by ex-Yammer execs that bills itself as a ‘WhatsApp for the workplace’, has launched a new feature to expand the circle of people who use the app: it now lets others send messages to those users via a URL on Cotap.me, without having to download the app itself.

It comes on the heels of a desktop app launch for the product in October that used some of the same functionality for Cotap-using work colleagues to communicate with each other when they were not on their mobile devices but at computers. Today’s launch effectively lets anyone use the chat functionality of the app, by way of the custom URLs that individuals give out.

Adding a web component to the app means that those who are Cotap users for work can now share their Cotap IDs with other people — as they would, say, a Skype or…

View original 419 more words

Featured Image -- 188

Reddit CEO Yishan Wong On Giving Stock To Users: “We Have A Crazy Plan.”

Originally posted on TechCrunch:

One of the defining ironies of the social networking IPOs over the last decade is that the financial returns have been concentrated among so few when the value has been created by so many.

But current Reddit CEO Yishan Wong wants to change that.

When Wong served as an early director at Facebook for five years, crypto-currencies were around, but they weren’t as widely accepted or understood as they are today. He and Y Combinator head Sam Altman, who just personally led a $50 million round in the company announced today, want to use them as a tool to distribute shares in the company back to the millions of Reddit users, or Redditors, that log in every day. They’ve set aside 10 percent of the round announced today for that purpose.

“Everybody who has ever run the company has always wanted to give some ownership back to the community somehow,” Wong said.

He went on, “We have a crazy plan and what…

View original 347 more words