Segment Trees Intro - Learning Module

Loading content...

0/276

Segment Tree Concept: Divide Intervals

Divide and Conquer Over Intervals

We've established that we need a hierarchical structure storing aggregates at multiple granularities. Now it's time to see exactly how segment trees achieve this.

A segment tree is a binary tree where:

Each node represents an interval (segment) of the array
Leaf nodes represent individual elements (intervals of length 1)
Internal nodes represent the combination of their children's intervals
The root represents the entire array

This divide-and-conquer structure over intervals is what gives segment trees their power. Any range can be decomposed into O(log n) node-intervals, and any element update propagates through only O(log n) nodes.

This page will take you through every aspect of the segment tree structure, from the conceptual model to concrete implementation details. By the end, you'll have complete mastery over how segment trees work.

What You Will Learn

By the end of this page, you will understand the complete segment tree structure: how intervals are divided, how the tree is stored in an array, how to build it in O(n), how queries decompose ranges, and how updates propagate. You'll see both the conceptual model and the practical implementation.

The Divide-and-Conquer Idea

The segment tree is built on a simple recursive insight:

To answer a query about range [L, R]:

If the range is small (a single element), return that element directly
Otherwise, split the range in half: [L, mid] and [mid+1, R]
Recursively answer for each half
Combine the results using our aggregation function

The key optimization:

Instead of recomputing these sub-ranges every time, we precompute them. Store the aggregate for every possible split point at every level of recursion.

This transforms the recursive algorithm into a tree structure where each node stores a precomputed aggregate. Queries just look up and combine the right nodes.

Visual Structure:

For array [a₀, a₁, a₂, a₃, a₄, a₅, a₆, a₇]:

                      [0-7]
                   /         \
              [0-3]           [4-7]
              /   \           /   \
          [0-1]   [2-3]   [4-5]   [6-7]
          /   \   /   \   /   \   /   \
         [0] [1] [2] [3] [4] [5] [6] [7]    (individual elements)

Each node stores the aggregate of its interval:
- [0-7] stores a₀ ⊕ a₁ ⊕ ... ⊕ a₇
- [0-3] stores a₀ ⊕ a₁ ⊕ a₂ ⊕ a₃
- [0-1] stores a₀ ⊕ a₁
- [0]   stores a₀

Properties of This Structure:

Perfect Binary Tree (for n = power of 2): Every internal node has exactly 2 children. When n isn't a power of 2, we can either pad or handle carefully.
Height = ⌈log₂ n⌉: Because we halve the interval at each level, the maximum depth is logarithmic.
Total Nodes ≤ 2n - 1: The sum 1 + 2 + 4 + ... up to n equals 2n - 1. We use O(n) space.
Each Element in Exactly log n Nodes: An element appears in its leaf, its parent, grandparent, etc., up to the root. Exactly ⌈log₂ n⌉ + 1 nodes.
Each Interval Node Represents a Power-of-2 Aligned Range: This alignment is key to the efficiency—intervals don't overlap, they perfectly tile the array.

These properties guarantee our target complexities:

Build: O(n) — visit each node once
Query: O(log n) — traverse at most O(log n) depth, visiting O(log n) nodes per level at worst
Update: O(log n) — propagate through exactly ⌈log₂ n⌉ + 1 ancestors

Why Binary?

We could split into more pieces (ternary, quaternary), but binary is optimal. More splits mean more children to combine per node (slower), but shorter trees (fewer levels). The mathematics work out such that binary (2 children) minimizes total work. This is why binary trees dominate data structures.

Array-Based Storage: The Implementation Trick

While conceptually a tree, segment trees are typically stored as a flat array. This is faster (better cache locality) and simpler (no pointer management).

The Indexing Scheme (1-indexed):

For a node at index i:

Left child: 2 * i
Right child: 2 * i + 1
Parent: ⌊i / 2⌋

The root is at index 1. Index 0 is unused (simplifies the math).

Example for n = 8:

Tree indices (1-indexed):
                        1
                     /     \
                   2         3
                 /   \     /   \
                4     5   6     7
               / \   / \ / \   / \
              8  9 10 11 12 13 14 15

Array tree[1..15]:
[unused, [0-7], [0-3], [4-7], [0-1], [2-3], [4-5], [6-7], 
         [0], [1], [2], [3], [4], [5], [6], [7]]

Note: The original array elements end up at indices n to 2n-1 (leaves).

segment_tree_storage.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * Segment Tree with Array-Based Storage
 * Using 1-indexed array for cleaner child/parent calculations
 */
class SegmentTree {
  private tree: number[];
  private n: number;
 
  constructor(arr: number[]) {
    this.n = arr.length;
    
    // Tree needs 4 * n space in worst case (for non-power-of-2 sizes)
    // For power-of-2, 2 * n suffices, but 4 * n is safe and simple
    this.tree = new Array(4 * this.n).fill(0);
    
    // Build the tree
    this.build(arr, 1, 0, this.n - 1);
  }
 
  /**
   * Build the tree recursively
   * @param arr - Original array
   * @param node - Current tree node index (1-indexed)
   * @param start - Start of current segment in original array
   * @param end - End of current segment in original array
   */
  private build(arr: number[], node: number, start: number, end: number): void {
    if (start === end) {
      // Leaf node: store the array element directly
      this.tree[node] = arr[start];
    } else {
      // Internal node: build children, then combine
      const mid = Math.floor((start + end) / 2);
      const leftChild = 2 * node;
      const rightChild = 2 * node + 1;
      
      this.build(arr, leftChild, start, mid);        // Build left subtree
      this.build(arr, rightChild, mid + 1, end);     // Build right subtree
      
      // Combine children (here: sum)
      this.tree[node] = this.tree[leftChild] + this.tree[rightChild];
    }
  }
 
  // Navigation helpers
  private leftChild(i: number): number { return 2 * i; }
  private rightChild(i: number): number { return 2 * i + 1; }
  private parent(i: number): number { return Math.floor(i / 2); }
}
 
/**
 * Space Analysis:
 * - For n elements, tree height h = ceil(log2(n))
 * - A perfect binary tree of height h has 2^(h+1) - 1 nodes
 * - For n = 10^6, h ≈ 20, so ~2^21 = 2*10^6 nodes ≈ 8MB (for int32)
 * - We allocate 4n to handle non-power-of-2 safely
 */

Why 4n Space?

When n isn't a power of 2, the tree isn't perfectly balanced. Some branches go deeper than others, potentially using more indices. The 4n allocation guarantees enough space for any n. In practice, 2n is usually enough, but 4n is a safe, simple choice that costs only a constant factor in memory.

Building the Tree: Bottom-Up Construction

The recursive build we saw is top-down: start at the root, recursively build children, then combine. But there's also an elegant bottom-up approach that's often faster in practice.

Bottom-Up Build (for n = power of 2):

Copy array elements to tree positions n to 2n-1 (leaves)
Fill internal nodes from n-1 down to 1, each = combine(left child, right child)

This processes each node exactly once, in a simple loop with no recursion.

Visual Example:

Array: [3, 1, 4, 1, 5, 9, 2, 6]

Step 1: Copy to leaves (positions 8-15)
tree[8..15] = [3, 1, 4, 1, 5, 9, 2, 6]

Step 2: Fill internals (positions 7 down to 1)
tree[7] = tree[14] + tree[15] = 2 + 6 = 8
tree[6] = tree[12] + tree[13] = 5 + 9 = 14
tree[5] = tree[10] + tree[11] = 4 + 1 = 5
tree[4] = tree[8] + tree[9] = 3 + 1 = 4
tree[3] = tree[6] + tree[7] = 14 + 8 = 22
tree[2] = tree[4] + tree[5] = 4 + 5 = 9
tree[1] = tree[2] + tree[3] = 9 + 22 = 31

Result: tree[1] = 31 (sum of all elements ✓)

build_segment_tree.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * Bottom-Up Segment Tree Build
 * Simple, fast, and elegant (for n = power of 2 or with padding)
 */
class BottomUpSegmentTree {
  private tree: number[];
  private n: number;
 
  constructor(arr: number[]) {
    this.n = arr.length;
    this.tree = new Array(2 * this.n).fill(0);
    
    // Step 1: Copy leaves (0-indexed: leaves at positions n to 2n-1)
    for (let i = 0; i < this.n; i++) {
      this.tree[this.n + i] = arr[i];
    }
    
    // Step 2: Build internals (positions n-1 down to 1)
    for (let i = this.n - 1; i >= 1; i--) {
      this.tree[i] = this.tree[2 * i] + this.tree[2 * i + 1];
    }
  }
  
  // Print tree structure for debugging
  printTree(): void {
    console.log("Segment Tree:");
    let level = 0;
    let levelStart = 1;
    while (levelStart < 2 * this.n) {
      const levelEnd = Math.min(levelStart * 2, 2 * this.n);
      const nodes = this.tree.slice(levelStart, levelEnd);
      console.log(`Level ${level}: ${nodes.join(', ')}`);
      levelStart = levelEnd;
      level++;
    }
  }
}
 
// Build complexity: O(n)
// - n copies for leaves
// - n-1 combines for internals
// Total: 2n - 1 = O(n)
 
const arr = [3, 1, 4, 1, 5, 9, 2, 6];
const st = new BottomUpSegmentTree(arr);
st.printTree();
 
/*
Output:
Level 0: 31
Level 1: 9, 22
Level 2: 4, 5, 14, 8
Level 3: 3, 1, 4, 1, 5, 9, 2, 6
*/

Top-Down vs Bottom-Up

Both approaches are O(n). Bottom-up is slightly faster due to better cache behavior and no recursion overhead. Top-down is more intuitive and easier to extend for complex operations (like lazy propagation). Choose based on context—bottom-up for simple cases, top-down for complex ones.

The Query Algorithm: Decomposing Ranges

Now for the key operation: answering a range query. The algorithm recursively decomposes the query range into precomputed segments.

The Core Insight:

For a query on [L, R], starting at the root (which covers [0, n-1]):

If the node's interval is completely outside [L, R]: return identity (0 for sum)
If the node's interval is completely inside [L, R]: return the stored value
Otherwise, query both children and combine results

Case 2 is the magic: when a node's interval fits entirely within our query range, we use its precomputed value instead of recursing further. This is where we save time.

Why O(log n)?

At each level, at most 2 nodes can have partial overlap with the query range. Fully-contained nodes return immediately. Nodes outside the range return immediately. Only nodes that straddle the query boundary recurse.

Since there are 2 boundary points (L and R) and at most 2 nodes per level can be at a boundary, we visit at most 4 nodes per level. With O(log n) levels, total is O(log n) nodes visited.

Visual Example: Query [2, 5] on array of size 8

                      [0-7] (partial overlap)
                   /             \
              [0-3] (partial)    [4-7] (partial)
              /     \             /       \
          [0-1]   [2-3]       [4-5]     [6-7]
        (outside) (inside!)  (inside!)  (outside)

Query(2, 5):
1. Root [0-7]: partial overlap → recurse to both children
2. Node [0-3]: partial overlap → recurse
3. Node [4-7]: partial overlap → recurse  
4. Node [0-1]: completely outside [2,5] → return 0
5. Node [2-3]: completely inside [2,5] → return stored value!
6. Node [4-5]: completely inside [2,5] → return stored value!
7. Node [6-7]: completely outside [2,5] → return 0

Result: combine values from [2-3] and [4-5]
No need to visit individual leaves!

segment_tree_query.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * Segment Tree Range Query Implementation
 */
class SegmentTreeWithQuery {
  private tree: number[];
  private n: number;
 
  constructor(arr: number[]) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.build(arr, 1, 0, this.n - 1);
  }
 
  private build(arr: number[], node: number, start: number, end: number): void {
    if (start === end) {
      this.tree[node] = arr[start];
    } else {
      const mid = Math.floor((start + end) / 2);
      this.build(arr, 2 * node, start, mid);
      this.build(arr, 2 * node + 1, mid + 1, end);
      this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
    }
  }
 
  /**
   * Query sum of elements in range [L, R]
   * Public interface - starts recursion from root
   */
  query(L: number, R: number): number {
    return this.queryHelper(1, 0, this.n - 1, L, R);
  }
 
  /**
   * Recursive query helper
   * @param node - Current tree node
   * @param start, end - Interval this node represents
   * @param L, R - Query range
   */
  private queryHelper(
    node: number, 
    start: number, 
    end: number, 
    L: number, 
    R: number
  ): number {
    // Case 1: Completely outside query range
    if (R < start || L > end) {
      return 0; // Identity element for sum
    }
    
    // Case 2: Completely inside query range — USE PRECOMPUTED VALUE
    if (L <= start && end <= R) {
      return this.tree[node];
    }
    
    // Case 3: Partial overlap — recurse to children
    const mid = Math.floor((start + end) / 2);
    const leftResult = this.queryHelper(2 * node, start, mid, L, R);
    const rightResult = this.queryHelper(2 * node + 1, mid + 1, end, L, R);
    
    return leftResult + rightResult;
  }
}
 
// Example usage:
const arr = [1, 3, 5, 7, 9, 11, 13, 15];
const st = new SegmentTreeWithQuery(arr);
 
console.log(st.query(0, 7));  // 64 (entire array)
console.log(st.query(2, 5));  // 5 + 7 + 9 + 11 = 32
console.log(st.query(0, 0));  // 1 (single element)
console.log(st.query(3, 3));  // 7 (single element)
console.log(st.query(1, 6));  // 3 + 5 + 7 + 9 + 11 + 13 = 48

The Power of Early Return

The magic is in Case 2: complete containment. Instead of recursing all the way to leaves (which would be O(n)), we return the precomputed aggregate. This is why building the tree pays off. The O(n) preprocessing enables O(log n) queries forever after.

The Update Algorithm: Propagating Changes

When an array element changes, we must update all tree nodes that include it in their interval. Since each element appears in exactly one node per level, this is exactly O(log n) updates.

The Algorithm:

Start at the root
Recursively find the leaf containing the updated index
Update the leaf with the new value
On the way back up, recompute each ancestor as combine(left child, right child)

Visual Example: Update index 3 to value 100

Before: arr[3] = 7 → After: arr[3] = 100 (delta = +93)

                    [0-7]     ← update: 64 → 157
                   /     \
              [0-3]       [4-7]
            ↑ update:       |
            9 → 102         |
              /   \         |
          [0-1]   [2-3]   (unchanged)
            |    ↑ update:
            |    12 → 105
            |      /   \
            |    [2]   [3] ← update: 7 → 100
            |     |
         (unchanged)

Only 4 nodes updated: [3], [2-3], [0-3], [0-7]
= O(log n) updates

segment_tree_update.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 * Segment Tree with Point Updates
 */
class SegmentTreeComplete {
  private tree: number[];
  private n: number;
 
  constructor(arr: number[]) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.build(arr, 1, 0, this.n - 1);
  }
 
  private build(arr: number[], node: number, start: number, end: number): void {
    if (start === end) {
      this.tree[node] = arr[start];
    } else {
      const mid = Math.floor((start + end) / 2);
      this.build(arr, 2 * node, start, mid);
      this.build(arr, 2 * node + 1, mid + 1, end);
      this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
    }
  }
 
  /**
   * Update element at index to new value
   * Public interface
   */
  update(index: number, value: number): void {
    this.updateHelper(1, 0, this.n - 1, index, value);
  }
 
  /**
   * Recursive update helper
   * @param node - Current tree node
   * @param start, end - Interval this node represents  
   * @param index - Array index to update
   * @param value - New value
   */
  private updateHelper(
    node: number,
    start: number,
    end: number,
    index: number,
    value: number
  ): void {
    if (start === end) {
      // Leaf node: update directly
      this.tree[node] = value;
    } else {
      const mid = Math.floor((start + end) / 2);
      
      if (index <= mid) {
        // Index is in left child's range
        this.updateHelper(2 * node, start, mid, index, value);
      } else {
        // Index is in right child's range
        this.updateHelper(2 * node + 1, mid + 1, end, index, value);
      }
      
      // Recompute this node after child update
      this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
    }
  }
 
  query(L: number, R: number): number {
    return this.queryHelper(1, 0, this.n - 1, L, R);
  }
 
  private queryHelper(node: number, start: number, end: number, L: number, R: number): number {
    if (R < start || L > end) return 0;
    if (L <= start && end <= R) return this.tree[node];
    const mid = Math.floor((start + end) / 2);
    return this.queryHelper(2 * node, start, mid, L, R) + 
           this.queryHelper(2 * node + 1, mid + 1, end, L, R);
  }
}
 
// Example demonstrating update:
const arr = [1, 3, 5, 7, 9, 11, 13, 15];
const st = new SegmentTreeComplete(arr);
 
console.log(st.query(2, 5)); // 5 + 7 + 9 + 11 = 32
 
st.update(3, 100);           // Change arr[3] from 7 to 100
console.log(st.query(2, 5)); // 5 + 100 + 9 + 11 = 125
 
st.update(4, 0);             // Change arr[4] from 9 to 0
console.log(st.query(2, 5)); // 5 + 100 + 0 + 11 = 116

Bottom-Up Point Update (Alternative):

Just like building, updates can be done iteratively from the bottom up:

1. Modify the leaf: tree[n + index] = value
2. Walk up to the root, recomputing each parent:
   for i = (n + index) / 2; i >= 1; i /= 2:
       tree[i] = tree[2*i] + tree[2*i+1]

This is often faster in practice due to lower overhead, though the recursive version is more intuitive and easier to extend.

Why We Recompute on the Way Up

After updating a leaf, every ancestor's stored value becomes stale. By recomputing bottom-up, we fix exactly the O(log n) nodes that need fixing. This is vastly better than prefix sums, where a single change could invalidate O(n) cached values.

Proof of Correctness and Complexity

Let's rigorously verify that segment trees achieve our target complexities.

Claim 1: Build is O(n)

Proof: The tree has at most 2n - 1 nodes (for n leaves, a complete binary tree has n - 1 internal nodes). Build visits each node exactly once, doing O(1) work per node (combining two children). Total: O(n). ∎

Claim 2: Query is O(log n)

Proof Sketch: At each level of the tree, at most 2 nodes have partial overlap with the query range [L, R].

The query range has two boundaries: L and R
At any level, the segment intervals partition the array
At most one segment can contain L in its interior (partial left overlap)
At most one segment can contain R in its interior (partial right overlap)
Segments fully inside or fully outside [L, R] don't recurse

So we visit at most 4 nodes per level: 2 partial overlaps, plus potentially 2 full containments that return immediately. With O(log n) levels, total nodes visited is O(log n).

A tighter analysis shows at most 2·log n nodes are visited, but O(log n) suffices. ∎

Claim 3: Point Update is O(log n)

Proof: A point update modifies exactly one path from leaf to root. The tree has height ⌈log₂ n⌉. At each level, we visit exactly one node (the ancestor containing the index). Total: O(log n) nodes, O(1) work per node. ∎

Claim 4: Space is O(n)

Proof: For a complete binary tree on n leaves, the number of nodes is exactly n + n/2 + n/4 + ... + 1 = 2n - 1. In practice, we allocate 4n to handle non-power-of-2 sizes and 1-indexing overhead. This is still O(n). ∎

Summary of Complexities:

Operation	Time	Space	Notes
Build	O(n)	O(n)	Visit each node once
Query	O(log n)	O(log n)*	O(log n) nodes visited; *stack space for recursion
Point Update	O(log n)	O(log n)*	Path from leaf to root
Total Space	—	O(n)	~4n in practice

These match our target from the previous page. Segment trees solve the dynamic range query problem optimally.

Mission Accomplished

We've achieved O(log n) for both queries and updates with O(n) space. Compare to prefix sums (O(1) query but O(n) update) or naive (O(n) query but O(1) update). Segment trees give us the best of both worlds—albeit with extra constant factors and implementation complexity.

Common Variations and Extensions

The basic segment tree we've built is just the starting point. Here are important variations you'll encounter:

1. Range Updates with Lazy Propagation

What if we want to update all elements in a range [L, R] at once? Naively updating each would be O(n). Lazy propagation defers updates, achieving O(log n) range updates. We'll cover this in a later module.

2. 2D Segment Trees

For matrices, we can nest segment trees. Each node of the outer tree (over rows) contains a segment tree over columns. This enables O(log² n) 2D range queries.

3. Persistent Segment Trees

When we need to query historical versions ("what was the sum at time T?"), persistent versions share structure between versions, achieving O(log n) per operation with O(log n) extra space per update.

4. Dynamic Segment Trees

For very large indices (like coordinates up to 10⁹), we can't allocate 4n nodes. Dynamic segment trees only create nodes that are actually used, achieving O(Q log n) space for Q operations.

When to Use Each Variation

•Basic Segment Tree — Point updates, range queries. The 90% case.
•Lazy Propagation — Range updates (add X to all elements in [L, R]).
•2D Segment Tree — Matrix operations, 2D range queries.
•Persistent — Version history, time-travel queries.
•Dynamic/Sparse — Very large coordinate spaces with few actual elements.
•Merge Sort Tree — Counting elements in a range that satisfy a condition.

Comparison with Fenwick Trees (BIT):

Fenwick trees (Binary Indexed Trees) are a simpler alternative for some operations:

Feature	Segment Tree	Fenwick Tree
Range sum	✓	✓
Range min/max	✓	✗ (normally)
Point update	✓	✓
Range update	✓ (with lazy)	Limited
Implementation	~50 lines	~15 lines
Constant factor	Higher	Lower
Versatility	Very high	Moderate

Fenwick trees are great for simpler problems (particularly prefix sums with updates). Segment trees are more versatile and essential for range minimum/maximum, range updates, and complex aggregations.

We'll explore Fenwick trees in a later module. For now, master segment trees—they're the more general tool.

The Segment Tree Mindset

Think of segment trees as a template, not just a data structure. The core idea—hierarchical decomposition with lazy combination—applies to many problems. Once you internalize the pattern, you can adapt it to novel situations: new operations, new constraints, new dimensions.

Summary: The Complete Segment Tree

We've covered the complete segment tree structure from concept to implementation. Let's consolidate:

Key Concepts Mastered

•Structure — A binary tree where each node represents an interval. Leaves are individual elements; internal nodes combine children.
•Array storage — Stored as a flat array using 2i and 2i+1 indexing for children. Uses O(n) space (4n safe allocation).
•Build — O(n) time. Either top-down recursive or bottom-up iterative. Each node computed once.
•Query — O(log n) time. Recursively decompose query range. Return precomputed values for fully-contained nodes.
•Update — O(log n) time. Traverse leaf-to-root path, recomputing each ancestor.
•Correctness — Guaranteed by hierarchical decomposition. At most O(log n) nodes at each level participate in any operation.

What's Next:

We've seen the segment tree with sum as the example operation. But segment trees work for ANY associative operation. The next page explores this versatility:

Range minimum: Finding the smallest element in a range
Range maximum: Finding the largest element in a range
Range GCD: Finding the greatest common divisor across a range
General template: How to adapt the structure for any associative operation

You'll see that only the combine function and identity element change—the structure remains exactly the same.

Segment Tree Mastery Achieved

You now understand how segment trees work at every level: the conceptual divide-and-conquer, the array-based implementation, the query and update algorithms, and the complexity proofs. Next, we'll see the structure in action with different operations.