Sum over a consecutive subsequence
Problem
Solve the Interval Product problem by create a set of functions that solve the following more abstract problem using Data.FingerTree.
Let's consider a sequence of elements in a monoid of $n$ elements, we are interested in the ability to modify an element in position i, insert/delete at position i, and calculate the sum of all elements between position i and j. All these operations should take $O(\log n)$ amortized time under the assumption that all monoid operation takes $O(1)$ time.
Motivation: This exercise shows that finger trees can replace binary indexed (Fenwick) trees. The abstract problem can be used to solve problems like Potentiometers and Frequent Values.
Solution
MonoidSequence.hs
{-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE FlexibleContexts #-} module MonoidSequence(MonoidSequence, splitPosition, update, insert, delete, infixSum, fromList) where import Data.FingerTree hiding (fromList) import qualified Data.FingerTree as F import Data.Monoid type MonoidSequence a = FingerTree (Sum Int, a) (S a) newtype S a = S a instance Monoid a => Measured (Sum Int, a) (S a) where measure (S x) = (Sum 1, x) splitPosition :: Measured (Sum Int, a) (S a) => Int -> MonoidSequence a -> (MonoidSequence a, MonoidSequence a) splitPosition i = split (\(Sum x,_)-> x > i) update :: Measured (Sum Int, a) (S a) => Int -> a -> MonoidSequence a -> MonoidSequence a update i entry tree = insert i entry (delete i tree) insert :: Measured (Sum Int, a) (S a) => Int -> a -> MonoidSequence a -> MonoidSequence a insert i entry tree = x >< singleton (S entry) >< y where (x,y) = splitPosition i tree delete :: Measured (Sum Int, a) (S a) => Int -> MonoidSequence a -> MonoidSequence a delete i tree = x >< y where (x,z) = splitPosition i tree (_,y) = splitPosition 1 z -- sum from position i to position j not inclusive infixSum :: Measured (Sum Int, a) (S a) => Int -> Int -> MonoidSequence a -> a infixSum i j tree = snd $ measure y where (_,z) = splitPosition i tree (y,_) = splitPosition (j-i) z fromList :: Monoid a => [a]-> MonoidSequence a fromList xs = F.fromList $ map S xs
IntervalProduct.hs
-- Interval Product -- ICPC Latin American Regional 2012 Problem I -- ACM-ICPC Live Archive Problem 6139 import MonoidSequence import Data.Monoid import Data.List.Split data Sign = N | Z | P deriving (Eq) instance Show Sign where show N = "-" show P = "+" show Z = "0" instance Monoid Sign where mempty = P mappend Z _ = Z mappend _ Z = Z mappend P x = x mappend x P = x mappend N N = P toSign :: Int -> Sign toSign x | x == 0 = Z | x > 0 = P | x < 0 = N main :: IO () main = interact process process :: String -> String process input = sol l where l = words input sol (n':k':xs) = solve (fromList values) operations ++ sol (drop (n+3*k) xs) where (n,k) = (read n', read k') values = map (toSign.read) (take n xs) operations = map (\[a,b,c]-> (a, read b, read c)) $ chunksOf 3 $ take (3*k) (drop n xs) sol _ = "" solve :: MonoidSequence Sign -> [(String, Int, Int)] -> String solve values ((a,b,c):operations) | a == "P" = show (infixSum (b-1) c values) ++ solve values operations | a == "C" = solve (update (b-1) (toSign c) values) operations solve _ [] = "\n"
